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"); }}