longest-common-subpath

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is a country of <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code>. In this country, there is a road connecting every pair of cities.

There are <code>m</code> friends numbered from <code>0</code> to <code>m - 1</code> who are traveling through the country. Each one of them will take a path consisting of some cities. Each path is represented by an integer array that contains the visited cities in order. The path may contain a city more than once, but the same city will not be listed consecutively.

Given an integer <code>n</code> and a 2D integer array <code>paths</code> where <code>paths[i]</code> is an integer array representing the path of the <code>ith</code> friend, return the length of the longest common subpath that is shared by every friend&#39;s path, or <code>0</code> if there is no common subpath at all.

A subpath of a path is a contiguous sequence of cities within that path.

&nbsp;
Example 1:

<pre>
Input: n = 5, paths = [[0,1,2,3,4],
 [2,3,4],
 [4,0,1,2,3]]
Output: 2
Explanation: The longest common subpath is [2,3].
</pre>

Example 2:

<pre>
Input: n = 3, paths = [[0],[1],[2]]
Output: 0
Explanation: There is no common subpath shared by the three paths.
</pre>

Example 3:

<pre>
Input: n = 5, paths = [[0,1,2,3,4],
 [4,3,2,1,0]]
Output: 1
Explanation: The possible longest common subpaths are [0], [1], [2], [3], and [4]. All have a length of 1.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>m == paths.length</code></li>
	<li><code>2 &lt;= m &lt;= 105</code></li>
	<li><code>sum(paths[i].length) &lt;= 105</code></li>
	<li><code>0 &lt;= paths[i][j] &lt; n</code></li>
	<li>The same city is not listed multiple times consecutively in <code>paths[i]</code>.</li>
</ul>

longestCommonSubpath

Longest Common Subpath

Reconstruct Itinerary

reconstruct-itinerary

重新安排行程

Maximum Length of Repeated Subarray

maximum-length-of-repeated-subarray

最长重复子数组

Array

Binary Search

Suffix Array

Hash Function

Rolling Hash

一个国家由 <code>n</code> 个编号为 <code>0</code> 到 <code>n - 1</code> 的城市组成。在这个国家里，每两个 城市之间都有一条道路连接。

总共有 <code>m</code> 个编号为 <code>0</code> 到 <code>m - 1</code> 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 重复 出现，但同一个城市在一条路径中不会连续出现。

给你一个整数 <code>n</code> 和二维数组 <code>paths</code> ，其中 <code>paths[i]</code> 是一个整数数组，表示第 <code>i</code> 个朋友走过的路径，请你返回 每一个 朋友都走过的 最长公共子路径 的长度，如果不存在公共子路径，请你返回 <code>0</code> 。

一个 子路径 指的是一条路径中连续的城市序列。

 

示例 1：

<pre>
输入：n = 5, paths = [[0,1,2,3,4],
 [2,3,4],
 [4,0,1,2,3]]
输出：2
解释：最长公共子路径为 [2,3] 。
</pre>

示例 2：

<pre>
输入：n = 3, paths = [[0],[1],[2]]
输出：0
解释：三条路径没有公共子路径。
</pre>

示例 3：

<pre>
输入：n = 5, paths = [[0,1,2,3,4],
 [4,3,2,1,0]]
输出：1
解释：最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。</pre>

 

提示：

<ul>
	<li><code>1 <= n <= 105</code></li>
	<li><code>m == paths.length</code></li>
	<li><code>2 <= m <= 105</code></li>
	<li><code>sum(paths[i].length) <= 105</code></li>
	<li><code>0 <= paths[i][j] < n</code></li>
	<li><code>paths[i]</code> 中同一个城市不会连续重复出现。</li>
</ul>