aspe的博客

#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

const int ML=100000;

string S,T;

int next[ML+10],ex[ML+10];

int main()
{
	cin>>S>>T;
	
	int lens=S.size(),lent=T.size();
	
	/*===================求next=====================*/ 

	next[0]=lent;
	
	for (int i=0; i<lent-1; i++) //暴力求 
	 if (T[i]==T[i+1]) next[1]++;
	 else break;
	
	int p=1;
	
	for (int i=2; i<lent; i++)
	{
		int u=p+next[p];
		
		if (i+next[i-p]<u) next[i]=next[i-p]; //全部答案 
		else                                  //部分答案 
		{
			int j=max(u,i);
			
			for ( ; j<lent && T[j]==T[j-i]; j++);
			
			next[i]=j-i; p=i;
		}
	}
	
	//for (int i=1; i<lent; i++) cout<<next[i]<<" ";
	//cout<<endl;
	
	/*===================求ex=====================*/ 
	
	for (int i=0; S[i]==T[i]; i++) ex[0]++; 
	
	p=0;
	
	for (int i=1; i<lens; i++)
	{
		int u=p+ex[p];
		
		if (i+next[i-p]<u) ex[i]=next[i-p];
		else
		{
			int j=u;
			
			for ( ; j<lens && S[j]==T[j-i]; j++);
			
			ex[i]=j-i; p=i;
		}
	}
	
	int ans=0;
	
	for (int i=0; i<lens; i++)
	 ans=max(ans,ex[i]);
	
	cout<<ans;
	
	return 0;
}