题目链接:UVA12467「Secret Word」 。
Alicia and Roberto like to play games. Today, Roberto is trying to guess a secret word that Alicia chose. Alicia wrote a long string Sin a piece of paper and gave Roberto the following clues:
abcd
then a
, abcd
, ab
, bc
and bcd
are some of the substrings of S but ac
, aa
, aabbccdd
and dcba
are not substrings of S) of S (possibly equal to S).Roberto knows Alicia very well, and he’s sure that if there are several possible secret words that satisfy the clues above, Alicia must have chosen the longest one.
Can you help him guess the secret word?
The first line of the input file contains a single integer number T \leq 150, the number of test cases.
T lines follow, each with a single stringS. S will only contain lowercase English letters. The length of Swill not exceed one million characters.
For each test case, output the secret word in one line.
Explanation of the sample cases:
colombia
: if you take c
and reverse it you get c
. colombia
starts with c
, so this satisfies the two clues above. Furthermore, c
is the longest word that satisfies the two clues so it must be the secret word.abcdba
: if you take ba
and reverse it you get ab
. abcdba
starts with ab
and there’s no longer substring that satisfies the two clues.neversayeven
: if you take even
and reverse it you get neve
. neversayeven
starts with neve
and there’s no longer substring that satisfies the two clues.neveroddoreven
: this case is a palindrome
so if we reverse it we get the same string. neveroddoreven
starts with neveroddoreven
(since they are the same) and obviously there’s no longer substring that satisfies that, so this is the secret word.listentothesilence
: Notice the secret word might be somewhere in the middle of the big word.5
colombia
abcdba
neversayeven
neveroddoreven
listentothesilence
c
ba
even
neveroddoreven
sil
#include <bits/stdc++.h>
using namespace std;
// 前缀函数
struct PrefixFunction {
#ifndef _PREFIXFUNCTION_
#define ll int
#define MAXN 2000005
#endif
ll pi[MAXN]; // 前缀函数
PrefixFunction() {}
// 计算前缀函数
void getPi(char *str, ll n) {
pi[0] = 0;
ll i = 1, j = pi[i-1];
while(i < n) {
if(str[i] == str[j]) {
pi[i++] = j++ + 1;
} else if(!j) {
pi[i++] = j;
} else {
j = pi[j-1];
}
}
}
};
int main()
{
static char str[MAXN];
static PrefixFunction pf;
ll t;
scanf("%d", &t);
for(ll k = 0; k < t; ++k) {
scanf("%s", str);
ll n = strlen(str);
for(ll i = 0, j = n-1; ~j; --j,++i) {
str[n+1+i] = str[j];
}
pf.getPi(str, 2*n+1);
ll ans = 0, pos;
for(ll i = n+1; i < 2*n+1; ++i) {
if(pf.pi[i] > ans) {
ans = pf.pi[i];
pos = i;
}
}
str[2*n-pos+ans] = '\0';
printf("%s\n", &str[2*n-pos]);
}
return 0;
}