Passward

题目描述

你来到了一个庙前，庙牌上有一个仅包含小写字母的字符串 s。
传说打开庙门的密码是这个字符串的一个子串 t，并且 t 既是 s 的前缀又是 s 的后缀并且还在 s 的中间位置出现过一次。

如果存在这样的串，请你输出这个串，如有多个满足条件的串，输出最长的那一个。
如果不存在这样的串，输出”Just a legend”(去掉引号)。

输入格式：

仅一行，字符串 s。

输出格式：

如题所述

样例输入

fixprefixsuffix

样例输出：

fix

数据范围：

对于 60%的数据， s 的长度<=100
对于 100%的数据， s 的长度<=100000

题解

hash 淼之

#include<cstdio>
#include<cstring>
using namespace std;
char s[2000005];
unsigned long long base = 31;
unsigned long long has[2000005];
unsigned long long Pow(unsigned long long b,int i)
{
    unsigned long long ans = 1;
    while(i)
    {
        if(i & 1)
            ans = ans * b;
        i >>= 1;
        b = b * b;
    }
    return ans;
}
int main()
{
    freopen("fool.in","r",stdin);
    freopen("fool.out","w",stdout);
    int q;
    scanf("%d",&q);
    while(q--){
        scanf("%s", s + 1);
        int len = strlen(s + 1);
        for (int i = 1; i <= len; i++)
        {
            has[i] = has[i - 1] * base + s[i];
        }
        int ans = 0;
        for (int i = 1; i <= len; i++)
        {
            unsigned long long T = Pow(base, i); 
            if( has[i] == has[len] - has[len - i] * T)
            {
                for(int j = 2; j < len - i; j++)
                {
                    if(has[j + i] - has[j] * T == has[i])
                    {
                        ans = i;
                        break;
                    }
                }
                if(ans != i)
                    break;
            }
        }
        if(ans)
        {
            for(int i = 1; i <= ans; i++)
            {
                printf("%c", s[i]);
            }
            printf("\n");
        }
        else 
            puts("---\n");
    }
}