记录编号	559124	评测结果	AAAAAAAAAA
题目名称	鱼的感恩	最终得分	100
用户昵称	tat	是否通过	通过
代码语言	C++	运行时间	2.923 s
提交时间	2021-02-17 10:47:39	内存使用	2.61 MiB

#include <bits/stdc++.h>
using namespace std; 
//鱼的感恩 ： kmp 
int main(int argc, char** argv) {
	freopen("fool.in","r",stdin);
	freopen("fool.out","w",stdout);
	int q;
	cin>>q;
	for(int k=1;k<=q;k++){
		int next[114514]={0};//也许不够 
		string str;
		cin>>str;
		int len=str.length();
		int j=0;
		for(int i=1;i<len;i++){
			while(j!=0&&str[i]!=str[j])j=next[j-1];
			if(str[i]==str[j])j++;
			next[i]=j; 
		}//求next数组
		int i;
		for(i=1;i<len;i++){
			if(next[i]==j)break;//j是整个串的前缀函数 
		} 
		if(i==len-1)j=next[j-1];//这说明此串本身的前缀和是其所有子串中最大的
		if(j==0){
			cout<<"---";
			continue;
		} 
		//cout<<j<<endl;
		for(int s=0;s<j;s++){
			cout<<str[s];
		} 
		cout<<endl;
		
	}
	return 0;
}