方法二：滑动窗口：枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式，计算它们相对位置相同的重复子数组即可。时间复杂度： O((N+M)×min(N,M)) 。
方法三：如果数组 A 和 B 有一个长度为 k 的公共子数组，那么它们一定有长度为 j≤k 的公共子数组。这样我们可以通过二分查找的方法找到最大的 k。而为了优化时间复杂度，在二分查找的每一步中，使用哈希的方法来判断数组 A 和 B 中是否存在相同特定长度的子数组。（搬运一下官网的讲解）
int findLength(vector<int>& A, vector<int>& B) {
int ret = 0;
int dp[B.size() + 1][A.size() + 1];
memset(dp, 0, sizeof(dp));
for(int i = B.size() - 1; i >= 0; i --){
for(int j = A.size() - 1; j >= 0; j --){
if(B[i] == A[j]){
dp[i][j] = dp[i + 1][j + 1] + 1;
}
ret = std::max(ret, dp[i][j]);
}
}
return ret;
}
int findLength(vector<int>& A, vector<int>& B) {
int ret = 0;
int dp[B.size() + 1][A.size() + 1];
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= A.size(); i ++){
for(int j = 1; j <= B.size(); j ++){
if(B[i - 1] == A[j - 1]){
// i 只与 i - 1 有关
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = 0;
}
ret = std::max(ret, dp[i][j]);
}
}
return ret;
}
// 优化到一维数组：第二层for循环我们使用的倒序的方式，这是因为dp数组后面的值会依赖
// 前面的值，而前面的值不依赖后面的值，所以后面的值先修改对前面的没影响，但前面的值
// 修改会对后面的值有影响，所以这里要使用倒序的方式。
int findLength(vector<int>& A, vector<int>& B) {
int ret = 0;
int dp[B.size() + 1];
memset(dp, 0, sizeof(dp));
for(int i = 0; i < A.size(); i ++){
for(int j = B.size(); j > 0; j --){
if(A[i] == B[j - 1]){
dp[j] = dp[j - 1] + 1;
}else{
dp[j] = 0;
}
ret = std::max(ret, dp[j]);
}
}
return ret;
}
int findLength(vector<int>& A, vector<int>& B) {
int ret = 0;
int m = A.size(), n = B.size();
for(int i = 0; i < m; i ++){
int p = i, q = 0;
int len = 0;
while(p < m && q < n){
len = A[p] == B[q] ? len + 1 : 0;
ret = max(ret, len);
p++, q++;
}
}
for(int i = 0; i < n; i ++){
int p = i, q = 0;
int len = 0;
while(p < n && q < m){
len = B[p] == A[q] ? len + 1 : 0;
ret = max(ret, len);
p++, q++;
}
}
return ret;
}
// 滑动窗口算法有个小优化，每次对齐后可以计算一下长度len是否已经小于或等于结果ret，
// 如果是，那我们就不用继续循环计算了，因为后面肯定没有更长的。
int base = 113;
int mod = 1e9 + 7;
// 求pow(base, len - 1),注意溢出问题
long helper(int i){
long res = 1;
long ref = base;
while(i != 0){
//如果是奇数次幂，先抽一个底数出来，提前乘到结果中
if(i % 2 != 0){
res = (res * ref) % mod;
}
//底数平方，幂减半
ref = (ref * ref) %mod;
i /= 2;
}
return res;
}
// 检验是否存在长度为len的公共子数组
bool check(std::vector<int>& A, std::vector<int>& B, int len){
// 算出A[0, len - 1]的哈希值
long hashA = 0;
for(int i = 0; i < len; i++)
hashA = (hashA * base + A[i]) % mod;
unordered_set<int> setA;
setA.insert(hashA);
// 根据公式递推后面对应长度的哈希值，并存入哈希表
long ref = helper(len - 1) ;
for(int i = 0; i < A.size() - len; i ++){
// +mod 是为了保证 hashA 大于0
hashA = ((hashA - A[i] * ref % mod + mod) % mod * base + A[i + len]) % mod;
setA.insert(hashA);
}
// 同样的方式处理B数组
long hashB = 0;
for(int i = 0; i < len; i++)
hashB = (hashB * base + B[i]) % mod;
if(setA.count(hashB))
return true;
for(int i = 0; i < B.size() - len; i++){
hashB = ((hashB - B[i] * ref % mod + mod) % mod * base + B[i + len]) % mod;
if(setA.count(hashB))
return true;
}
return false;
}
int findLength(vector<int>& A, vector<int>& B) {
// [left, right]是所有可能不存在“对应长度的公共子数组”的集合
// （0是一定存在的，所以left从1开始，min(A.size() , B.size()) + 1
// 是一定不存在的，所以也需要包含在内）
int left = 1;
int right = min(A.size(), B.size()) + 1;
while(left < right){
int mid = left + (right - left) / 2;
if(check(A, B, mid))
left = mid + 1;
else
right = mid;
}
return left - 1;
}
