leetcode 718 最长的公共子数组长度

题目描述详见

Maximum Length of Repeated Subarray - LeetCode?

leetcode.com

一句话描述：求两个int数组的最长公共子数组长度。

例如：

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].

而且int值的范围是不超过100的非负整数，数组大小不超过1000.

（低效的）思路1：动态规划。

由于题目暗示了输入规模不大，因此可以考虑动态规划。这里的难点是如何抽象子问题。

动态规划要求子问题有一定重叠性，否则就是分治法了。观察上面的例子，A和B的最大子数组，其实也就是[1,2,3,2,1]和[3,2,1]的最大后缀公共子数组。因此抽象子问题为：A[0,i]和B[0,j]的最大后缀公共子数组。子问题规模是A和B的长度乘积，由于输入规模不超过1000，因此问题规模不超过100万，占用内存4MB位元组。

动态规划的代码不贴了，运行效率显然是O(MN)，空间复杂度也是O(MN)；最终OJ运行时间110-120ms左右，只打败了20%的用户；

于是看了一下discuss，一个标题吸引了我，其中的关键词rabin-karp令人拍案叫绝！我没有读他的代码（事实上也很难读懂），而是根据rabin-karp这个提示，立即写出了O((M+N)lg(min(M,N))复杂度的演算法，击败了100%用户；运行时间12ms左右，足足比动态规划提高了10倍！

思路2：Rabin-Karp演算法

Rabin-Karp演算法简介：

该演算法是一种基于hash指纹的字元串匹配演算法，演算法并不复杂，类似于暴力的字元串匹配演算法。但由于使用了hash预处理，使得匹配十分高效，基本是线性复杂度，只有在理论情况下退化到M*N复杂度。

以两个数字字元串匹配举个例子：

文本串："37826827826"

模式串："827"

我们尝试在文本串中查找模式串的出现位置。

首先需要选择一个hash函数，将模式串转为hash值，这里简单考虑，使用求模取余的方法。

[] (int v) {

return v % 13; // 不是一个好的函数，为了故意制造hash冲突这样写的。

}

计算得知模式串的hash值是8；

现在开始执行匹配过程，从文本串起始位置开始：

计算378的hash值，为1，不匹配，向右继续寻找；

计算782的hash值，为2，不匹配，向右继续寻找；

...

当计算到268的时候，hash为8，与模式hash值相等，

由于hash冲突，我们需要进一步确认串是否相等，显然不相等，因此这是一个伪命中；

随后匹配827的时候，才是真正的命中。

复杂度分析：

预计算hash值：O(M)

匹配过程: O(N-M+1)计算hash值，O(N-M+1)的匹配过程。

由于伪命中会导致效率降低，但实际使用中，恰当选择hash函数，几乎可以完全避免伪命中。

好了，演算法简介到此结束，你是否能根据启发写出解答呢？

具体过程不再叙述，代码如下：

int findLength(vector<int>& A, vector<int>& B) { if (A.empty() || B.empty()) return 0;

if (A.size() > B.size())
A.swap(B);

const int kPrime = 101; // 基数大于max_value(A, B), 不可能有伪命中
const size_t len = B.size();

// 预计算kPrime进位下的`1，10，一百`等等的值。
vector<int> power(A.size());
power[0] = 1;
for (size_t i = 1; i < len; ++i) {
power[i] = power[i-1] * kPrime;
}

size_t low = 1, high = A.size();
while (low <= high) {
// 尝试testlen的子数组是否能匹配上
const size_t testLen = (low + high) / 2;
assert (testLen >= 1);

unordered_set<int> fingerA;
int prevHash = 0;
// 预计算A的hash值
for (int i = 0; i + testLen <= A.size(); ++i) {
int hash = prevHash;
if (i == 0) {
for (int j = i; j < i+testLen; ++j) {
hash = hash * kPrime + A[j];
}
} else {
hash -= A[i-1] * power[testLen-1];
hash *= kPrime;
hash += A[i+testLen-1];
}
fingerA.insert(hash);
prevHash = hash;
}

prevHash = 0;
bool matched = false;
// 检查A和B是否有匹配指纹
for (int i = 0; !matched && i + testLen <= B.size(); ++i) {
int hash = prevHash;
if (i == 0) {
for (int j = i; j < i+testLen; ++j) {
hash = hash * kPrime + B[j];
}
} else {
hash -= B[i-1] * power[testLen-1];
hash *= kPrime;
hash += B[i+testLen-1];
}