[各種面接問題]重なる長男串

重複する長男の列:
タイトルの説明:
2つの文字列を与え、それらが前後に重なる最長子列の長さを求める.例えば、「abcde」と「cdefg」は「cde」であり、長さは3である.
入力:
入力には、複数のテストケースが含まれる場合があります.各テストケースには1行のみで、2つの文字列が含まれています.文字列の長さは1000000を超えず、文字'a'-'z'のみが含まれます.
出力:
各テストケースに対応して,それらが前後に重なる最長子列の長さを出力する.
サンプル入力:

abcde cdefg

サンプル出力:

3

第1の反応はやはり接尾辞の配列で、aとbをつなぎ合わせて、接尾辞の配列のhの配列を求めて、それから答えを探す時bソースの列のこの接尾辞を探してそれからaと始まるある接尾辞のhの最小値の中の最大値を探して、このようにすべきです.このステップがhを求めた後に線形時間で求められるかどうか考えてみましょう..
接尾辞の配列は先に置いて、别に考えて、KMPととても似ていると感じて、ある接尾辞とある接頭辞の最大の似ている长さを求めて、実はKMPの第1部で、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
",ans);
	}
}

それから問題解を見て、人はKMPを拡張して、思想はKMPと似ていますが、私はもっと最大の回文子列に似ていて、すでに得た範囲を利用して現在の値を更新していると思います.
ここに図がありますが、見ると分かりやすいです.
http://blog.sina.com.cn/s/blog_6974c8b20101054d.html
KMPを拡張する2つのステップは似ています.

#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