记录编号	414462	评测结果	AAAAAAAAAA
题目名称	鱼的感恩	最终得分	100
用户昵称	ONCE AGAIN	是否通过	通过
代码语言	C++	运行时间	0.794 s
提交时间	2017-06-14 11:29:08	内存使用	6.01 MiB

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZEN = 1000100;
int fail[SIZEN] = {0},n;
char str[SIZEN] = {0};
bool flag[SIZEN] = {0};
void KMP_INIT(){
	int j = 0;
	for(int i = 2;i <= n;i++){
		while(j && str[j+1]!=str[i])j = fail[j];
		if(str[j+1] == str[i])j++;
		fail[i] = j;
	}
	int ans = 0;
	memset(flag,0,sizeof flag);
	for(int i = 2;i < n;i++)flag[fail[i]] = true;
	for(int i = n;i;i=fail[i])if(flag[i]){ans = i;break;}
	if(ans == 0)puts("---");
	else {for(int i = 1;i <= ans;i++)putchar(str[i]);puts("");}
}
int main(){
    freopen("fool.in","r",stdin);
	freopen("fool.out","w",stdout);
	int Q;scanf("%d",&Q);
	while(Q--){
		scanf("%s",str+1);
		n = strlen(str+1);
		KMP_INIT();
	}
	return 0;
}