371 字
2 分钟
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");
}
}