记录编号	434228	评测结果	AAAAAAAAAA
题目名称	鱼的感恩	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.401 s
提交时间	2017-08-07 14:31:34	内存使用	0.79 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
char s[100500];
int n,nxt[100500];
bool bo;
void getnext(){
	memset(nxt,0,sizeof nxt);
    nxt[0]=-1;
    for(int i=1,j=-1;i<=n;i++){
        while(~j&&s[j+1]!=s[i]) j=nxt[j];
        nxt[i]=++j;
    }
}
int main()
{
	freopen("fool.in","r",stdin);
	freopen("fool.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		bo=0;
	    scanf("%s",s+1);
	    n=strlen(s+1);
	    getnext();
	    if(nxt[n]==0){printf("---\n");continue;}
	    for(int i=nxt[n]+1;i<n;i++){
	        if(nxt[i]==nxt[n]){
	            for(int j=1;j<=nxt[n];j++)
	                printf("%c",s[j]);
	            printf("\n");bo=1;break;
	        }
	    }
	    if(bo==1) continue;
	    for(int i=n-nxt[n]+2;i<=n;i++){
	        if(s[i]==s[1]){
	            int j;
	            for(j=1;i+j-1<=n;j++)
	                if(s[i+j-1]!=s[j]) break;
	            if(i+j-1>n){
	                j--;
	                for(int k=j+1;k<n;k++){
	                    if(nxt[k]==j){
	                        for(int l=1;l<=j;l++)
	                            printf("%c",s[l]);
	                        printf("\n"); bo=1;
	                        break;
	                    }if(bo==1) break;
					}
	            }
	        }if(bo==1) break;
	    }if(bo==1) continue;
	    printf("---\n");continue;
	}
    return 0;
}
/*
1
bbabaaabaaaabaaabbaaabaaabaabbaaaaabbabbbaaaaabbabbabbaababbbbabbaabbbbbabbaabaaabbaaabbaabababaaabbbaaaaaaaabbbaabaabbbbaababbbabbbbbaabaabbabbbbaaaabbabbbbbaaaaaaababaababaabbaaaaabbbaaabaabbbbbbaaaaaaabbbbbbaaababbbbbbaaabbbaabaabbbbaaabbbbaabbabbbabbaabbaaaabbbbaabaaabaaaabaaaaaaabbbbabbaaaabababaabbbbbaabbbbbaaabbbbaabaabaaabaababbabbbaabbbaababbabbbabbacabaaabaaabbaba
*/