记录编号	414828	评测结果	AAAAAAAAAA
题目名称	鱼的感恩	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	2.009 s
提交时间	2017-06-15 09:28:08	内存使用	4.88 MiB

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 1010000
using namespace std;
char a[N],b[N];
int fail[N];
int len;
int l;
void getfail(int le)
{
     fail[0]=fail[1]=0;
     int k=0;
     pos(i,2,le)
     {
         while(k&&a[k]!=a[i-1])
           k=fail[k];
         if(a[k]==a[i-1])
           k++;
         fail[i]=k;
     }
}
int t;
int check(int le)
{
    int k=0;
    pos(i,0,len-1)
    {
        while(k&&a[k]!=b[i])
          k=fail[k];
        if(a[k]==b[i])
          k++;
        if(k==le)
        {
           //cout<<"le="<<le<<"  len="<<len<<endl;
           if(le==fail[len])
           {
              //cout<<"sha"<<endl;
              if(i!=len-1&&i!=le-1)
                return 1;
           }
           else
           {   
               if(i==len-1)
                 return 1;
           }
           k=fail[k];    
        }
    }
    return 0;
}
int haha()
{
    freopen("fool.in","r",stdin);
    freopen("fool.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
            memset(fail,0,sizeof(fail));
            scanf("%s",a);
            strcpy(b,a);
            len=strlen(a);
            getfail(len);
            l=fail[len];
            //cout<<fail[len];
            //pos(i,1,len)
              //cout<<fail[i]<<endl;
            while(1)
            {
               //cout<<"l="<<l<<"  len="<<len<<endl;
               if(check(l)) break;
               
               l=fail[l];
               if(l<=0)
                break;
            }
            if(l<=0)
               printf("---\n");
            else
            {
              a[l]='\0';
              puts(a);
              /*pos(i,0,fail[l]-1)
                 cout<<a[i];
              cout<<endl;*/
              
            }
                 
    }
    //while(1);
    return 0;
}
int sb=haha();
int main()
{;}