题目描述：

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

题目大意：

给定整数数组A和B，求其最长公共连续子串。

解题思路：

动态规划（Dynamic Programming）

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和KMP的解法，但是均返回Time Limit Exceeded

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

 

本文链接：http://bookshadow.com/weblog/2017/10/29/leetcode-maximum-length-of-repeated-subarray/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码