学步园

重叠的最长子串：

题目描述：

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

输入：

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

输出：

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

样例输入：

abcde cdefg

样例输出：

3

 第一反应还是后缀数组，把a跟b串起来，求后缀数组的h数组，之后找答案的时候就找b源串这个后缀然后跟a起始的某个后缀的h的最小值中的最大值，应该是这样。想一想这一步在求得h之后能否在线性时间求得。。。

后缀数组先放一放，另外想了下，觉得跟KMP是很相似的，就是求某一个后缀跟某一个前缀最大相似长度，其实就是KMP的第一部，构造PRE数组。首先是构造新串
 t= b+a；这样就变成a的后缀跟b的前缀最大相似长度了。

注意最后返回的时候不能直接返回pre[t.length()-1]+1, 还要判断是否超过a的长度。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;

char a[1000005];
char b[1000005];

int longestCover(string& a,string& b)
{
	string t(b+a);
	vector<int> pre(t.length(),-1);
	for(int i=1;i<t.length();i++)
	{
		int p=pre[i-1];
		while(p!=-1&&t[p+1]!=t[i])
			p=pre[p];
		if(t[p+1]==t[i])
			pre[i]=p+1;
	}
	return min((int)a.length(),pre[t.length()-1]+1);
}
int main()
{
	while(scanf("%s%s",a,b)!=EOF)
	{
		string aa(a),bb(b);
		int ans=longestCover(aa,bb);
		printf("%d\n",ans);
	}
}

然后看了下题解，人家用的是扩展KMP，思想跟KMP很像，但是我觉得更像最大回文子串，都是利用已经得到的范围来更新当前值。

这里有张图，看了就比较容易理解了：

http://blog.sina.com.cn/s/blog_6974c8b20101054d.html

扩展KMP的两步很相似。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int getLonestCover(string& s,string& t)
{
	vector<int> a(t.length(),0);
	a[0]=t.length();
	int len=0;
	while(1+len<t.length()&&t[len]==t[1+len])
		len++;
	a[1]=len;
	int k=1,mx=k+a[k]-1;
	for(int i=2;i<t.length();i++)
	{
		int w=i-k;
		if(i+a[w]-1<mx)
			a[i]=a[w];
		else
		{
			int len=max(0,mx-i+1);
			while(i+len<t.length()&&t[0+len]==t[i+len])
				len++;
			a[i]=len;
			k=i,mx=i+a[i]-1;
		}
	}
	vector<int> b(s.length(),0);
	len=0;
	while(len<s.length()&&len<t.length()&&s[len]==t[len])
		len++;
	b[0]=len;
	k=0,mx=len-1;
	for(int i=1;i<s.length();i++)
	{
		int w=i-k;
		if(i+a[w]-1<mx)
			b[i]=a[w];
		else
		{
			int len=max(0,mx-i+1);
			while(i+len<s.length()&&len<t.length()&&s[i+len]==t[len])
				len++;
			b[i]=len;
			k=i,mx=i+b[i]-1;
		}
	}
	int ans=0;
	for(int i=0;i<s.length();i++)
		if(b[i]==s.length()-i)
		{
			ans=b[i];
			break;
		}
	return ans;
}
int main()
{
	string a,b;
	while(cin>>a>>b)
	{
		int ret=getLonestCover(a,b);
		cout<<ret<<endl;
	}
}

然后贴一个扩展KMP的题：http://blog.csdn.net/xingyeyongheng/article/details/9386671