记录编号	434225	评测结果	AAAAAAAAAA
题目名称	鱼的感恩	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	4.747 s
提交时间	2017-08-07 14:27:36	内存使用	1.74 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long BASE=23333;
const int maxn=100005;
unsigned long long HA[maxn],poww[maxn];
char s[maxn];
unsigned long long getha(int l,int r)
{
    return HA[r]-HA[l-1]*poww[r-l+1];
}
int len;
bool check(int val)
{
    unsigned long long s1=getha(len-val+1,len),s2=getha(1,val);
    if(s1!=s2)return 0;
    for(int i=2;i<=len-val;i++)
    {
        unsigned long long s3=getha(i,i+val-1);
        if(s3==s1)
            return 1;
    }
    return 0;
}
int haha()
{
    freopen("fool.in","r",stdin);
    freopen("fool.out","w",stdout);
    int n;scanf("%d",&n);
    while(n--)
    {
        scanf("%s",s+1);len=strlen(s+1);
        poww[0]=1;
        for(int i=1;i<=100000;i++)poww[i]=poww[i-1]*BASE;
        HA[0]=0;
        for(int i=1;i<=len;i++)
        {
            HA[i]=HA[i-1]*BASE+s[i]-'a';
        }
        int ans=0;
        for(int i=len-2;i;i--)
            if(check(i)){ans=i;break;}
        if(!ans)puts("---");
        else 
        {
            for(int i=1;i<=ans;i++)putchar(s[i]);
            puts("");
        }
    }
}
int sb=haha();
int main(){;}