记录编号	192184	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 牛棚回声	最终得分	100
用户昵称	stone	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-10-09 21:43:36	内存使用	0.35 MiB

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

using namespace std;

int next[10001];
int Ans = 0;
string s1,s2;
string s3,s4;

void getfail(const char*,int*);
int main(){
	freopen("echo.in","r",stdin);
	freopen("echo.out","w",stdout);
	cin >> s1 >> s2;
	s3 = s1+s2;
	getfail(s3.c_str(),next);
	Ans = max(Ans,next[s3.length()]);
	memset(next,0,sizeof next);
	s4 = s2+s1;
	getfail(s4.c_str(),next);
	Ans = max(Ans,next[s4.length()]);
	cout << Ans;
}

void getfail(const char *P,int *next){
	int m = strlen(P);
	next[0] = next[1] = 0;
	for(int i = 1;i < m;++ i){
		int j = next[i];
		while(j && P[i] != P[j])
		    j = next[j];
		next[i+1] = P[i] == P[j] ? j+1 : 0;
	}
}
/*void KMP(const char*P,const char* T,int* next){
	int n = strlen(P),m = strlen(T);
	int j = 0;
	getfail(T,next);
	for(int i = 0;i < n;++ i){
		while(j && P[i] != T[j])
		    j = next[j];
		if(P[i] == T[j])
		    j ++;
		if(j == )
	}
}*/