【9度0J】 题目1535：重叠的最长子串 （扩展KMP算法）（滚动哈希算法-Rabin-Karp算法）

【九度0J】 题目1535：重叠的最长子串 （扩展KMP算法）（滚动哈希算法--Rabin-Karp算法）

题目描述：

给定两个字符串，求它们前后重叠的最长子串的长度，比如"abcde"和“cdefg”是"cde"，长度为3。

输入：

输入可能包含多个测试案例。
对于每个测试案例只有一行， 包含两个字符串。字符串长度不超过1000000，仅包含字符'a'-'z'。

输出：

对应每个测试案例，输出它们前后重叠的最长子串的长度。

样例输入：

abcde cdefg

样例输出：

3

思路：扩展KMP，用extend[i]保存 主串 S[i.....n-1]与 模式串 T的最长公共前缀的长度，其中n是S的长度。

然后扫描一遍 extend[] 如 extend[i] == n-i 那么这个后缀的长度就是我们要求的值。

关于扩展KMP，可以去看论文：《求最长回文子串与最长重复子串》何林 的集训队论文

代码：

#include <iostream>#include <string>#include <cstddef>#include <cstdlib>using namespace std;typedef unsigned long long ull;const ull B = 100000007;int overlap(string &a,string &b){int alen = a.size(), blen = b.size();int res = 0;ull ahash = 0, bhash = 0, t = 1;for(int i = 1; i <= min(alen,blen); i++){ahash = ahash + (a[alen-i]-'a')*t; //a的长度为i的后缀哈希值bhash = bhash*B + b[i-1]-'a';  //b的长度为i的前缀哈希值if(ahash == bhash) res = i;t *= B; }return res;} int main(){string a,b;while(cin>>a>>b){cout<<overlap(a,b)<<endl;}return 0;}

顺便说一下：不同字符串的哈希值发生冲突的概率非常低，通常可以忽略朴素的检查。