## 题目描述：

LeetCode 718. Maximum Length of Repeated Subarray

Given two integer arrays `A` and `B`, return the maximum length of an subarray that appears in both arrays.

Example 1:

```Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
```

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

## 解题思路：

dp[i][j]表示A串中第i个字符，B串中第j个字符结尾的最长公共子串的长度

```dp[i][j] = dp[i - 1][j - 1] + 1     if A[i] == B[j]

dp[i][j] = 0                  otherwise```

## Python代码：

``````class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
sa, sb = len(A), len(B)
dp = [0] * sb
ans = 0
for x in range(sa):
ndp = [0] * sb
for y in range(sb):
if A[x] == B[y]:
ndp[y] = 1
if x and y:
ndp[y] += dp[y - 1]
ans = max(ans, ndp[y])
dp = ndp
return ans
``````

Trie树解法（Time Limit Exceeded）

## Python代码：

``````class TrieNode:
def __init__(self):
self.children = dict()

class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
sa, sb = len(A), len(B)
root = TrieNode()
for x in range(sa):
node = root
for y in range(x, sa):
num = A[y]
child = node.children.get(num)
if child is None:
child = TrieNode()
node.children[num] = child
node = child

ans = 0
for x in range(sb):
cnt = 0
node = root
for y in range(x, sb):
num = B[y]
node = node.children.get(num)
if node is None: break
cnt += 1
ans = max(ans, cnt)
return ans
``````

KMP解法（Time Limit Exceeded）

## Python代码：

``````class Solution(object):
def findLength(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
sa, sb = len(A), len(B)
ans = 0
for x in range(sa):
size = sa - x
next = [0] * size
for i in range(1, size):
k = next[i - 1]
while A[i + x] != A[k + x] and k:
k = next[k - 1]
if A[i + x] == A[k + x]:
next[i] = k + 1
z = 0
for y in range(sb):
if z >= size: break
while z and A[z + x] != B[y]:
z = next[z - 1]
if A[z + x] == B[y]:
z += 1
ans = max(ans, z)
return ans
``````

Pingbacks已关闭。