718. Maximum Length of Repeated Subarray #

Problem #

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 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Problem Summary #

Given two integer arrays A and B, return the length of the longest common subarray in the two arrays.

Solution Approach #

Given two arrays, find the length of the longest identical substring in the two arrays.
The easiest solution to think of for this problem is DP. dp[i][j] represents the length of the longest identical substring between the substring starting at index i in array A and the substring starting at index j in array B. The state transition equation is dp[i][j] = dp[i+1][j+1] + 1 (when A[i] == B[j]). The time complexity of this solution is O(n^2), and the space complexity is O(n^2).
The best solution for this problem is binary search + Rabin-Karp. The time-consuming part of comparing identical substrings is that it requires a loop to traverse all characters in the substring. But comparing two numbers is fast, with O(1) time complexity. So someone thought: can strings also be mapped to numbers? This would make comparison very fast. This algorithm is the Rabin-Karp algorithm. Mapping a string to a number cannot be arbitrary; it also needs to support dynamic growth based on the string prefix, so that when comparing the next string, the previously compared prefix can be used to speed up subsequent string comparisons. In the Rabin-Karp algorithm, there is a concept of a “code point”, similar to the base in decimal notation. For a detailed explanation of the algorithm, see this article:
Basic Knowledge - Rabin-Karp Algorithm
The “code point” is generally chosen as a prime number. In Go’s strings package, the value used is 16777619. So this problem can also directly use this value. Since this time we are required to find the longest length, use the longest length as the target for binary search. First, hash the numbers in array A and array B using Rabin-Karp according to the binary-searched length. Map the hashes in A to their indices and store them in a map for fast lookup later. Then traverse the hashes in B. When a hash matches, match the indices again. If the index exists and has the same prefix, then an identical substring has been found. Finally, continuously binary search to find the longest result. The time complexity of this solution is O(n * log n), and the space complexity is O(n).

Code #


package leetcode

const primeRK = 16777619

// Solution 1: Binary Search + Rabin-Karp
func findLength(A []int, B []int) int {
	low, high := 0, min(len(A), len(B))
	for low < high {
		mid := (low + high + 1) >> 1
		if hasRepeated(A, B, mid) {
			low = mid
		} else {
			high = mid - 1
		}
	}
	return low
}

func hashSlice(arr []int, length int) []int {
	// The hash array records the hash values of the parts of arr that exceed length
	hash, pl, h := make([]int, len(arr)-length+1), 1, 0
	for i := 0; i < length-1; i++ {
		pl *= primeRK
	}
	for i, v := range arr {
		h = h*primeRK + v
		if i >= length-1 {
			hash[i-length+1] = h
			h -= pl * arr[i-length+1]
		}
	}
	return hash
}

func hasSamePrefix(A, B []int, length int) bool {
	for i := 0; i < length; i++ {
		if A[i] != B[i] {
			return false
		}
	}
	return true
}

func hasRepeated(A, B []int, length int) bool {
	hs := hashSlice(A, length)
	hashToOffset := make(map[int][]int, len(hs))
	for i, h := range hs {
		hashToOffset[h] = append(hashToOffset[h], i)
	}
	for i, h := range hashSlice(B, length) {
		if offsets, ok := hashToOffset[h]; ok {
			for _, offset := range offsets {
				if hasSamePrefix(A[offset:], B[i:], length) {
					return true
				}
			}
		}
	}
	return false
}

// Solution 2: DP Dynamic Programming
func findLength1(A []int, B []int) int {
	res, dp := 0, make([][]int, len(A)+1)
	for i := range dp {
		dp[i] = make([]int, len(B)+1)
	}
	for i := len(A) - 1; i >= 0; i-- {
		for j := len(B) - 1; j >= 0; j-- {
			if A[i] == B[j] {
				dp[i][j] = dp[i+1][j+1] + 1
				if dp[i][j] > res {
					res = dp[i][j]
				}
			}
		}
	}
	return res
}