rockdu
411. Petya the Hero
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
Memory limit: 65536 kilobytes
input: standard
output: standard
output: standard
Petya has come back from the Berland-Birland War, and now he is fond of gathering his friends and narrating his heroic deeds. You have probably heard the story telling that Petya, being isolated, captured two Birland officers single-handed, than, using their clothes and having got to know the password, penetrated into the army base of the enemy, forced the controlling system out of action and helped Berland army to seize the base. This story was also heard by Colonel Kruglyakovsky, who was especially interested in a detail. That is the way Petya managed to find out the password for entering the army base with his poor knowledge of Birland language. Called by the colonel young hero explained, that although Birland speech wasn't clear to him, it wasn't too difficult to write it down. At first Petya interrogated the captives and wrote down the speech of each one as a string of latin letters. He knew that Birland valid passwords could be read the same way in either direction, i.e. they were palindromes. So he had to use the program, searching for the longest common substring of two strings, which was valid as a password. After hearing the answer, Colonel Kruglyakovsky declared, that this program could be very useful for interrogation captives and for decoding secret messages... As far as Petya certanly hadn't any program, he asked you for help.
Input
The input file contains two non-empty strings that consist of lowercase latin letters ('a'-
'z'). The length of each string doesn't exceed 2000 symbols. The strings contain at least one common letter.
Output
Output the password obtained by the program Petya has described. If there are several possible passwords, output any of them. Example(s)
sample input | sample output |
abacaba abracab | aca |
sample input | sample output |
abbab babbab | abba |
前几天在脑补：我们会O(n)求LCS，还会O(n)求最长回文子串，那么我们可不可以求最长公共回文子串呢？（没想到真的有这种题！！）于是就简单脑补了一下。求最长公共回文串，想到用回文自动机。一个串建立自动机一个串跑，然后边跑边更新最大的匹配长度就好了（类似后缀自动机匹配，具体见代码）。多个串也可以类似后缀自动机的处理。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
char s[maxn], word[maxn];
namespace PAM {
char * s;
int trie[maxn][26], sum[maxn], fail[maxn], len[maxn], fa[maxn], pid[maxn];
int cnt, pos, last;
void init(char * str) {
cnt = 1, pos = last = 0, s = str;
fail[0] = 1, len[0] = 0, len[1] = -1;
}
int getfail(int p) {
while(s[pos - len[p] - 1] != s[pos])
p = fail[p];
return p;
}
void add(int x) {
int id = s[x] - 'a';
int p = getfail(last);
if(!trie[p][id]) {
int now = ++cnt;
fail[now] = trie[getfail(fail[p])][id];
trie[p][id] = now;
fa[now] = p, pid[now] = id;
len[now] = len[p] + 2;
}
last = trie[p][id];
++sum[last];
}
void push_up() {
for(register int i = cnt; i >= 0; --i)
sum[fail[i]] += sum[i];
}
void create() {
int sl = strlen(s);
for(register int i = 0; i < sl; ++i)
pos = i, add(i);
push_up();
}
int work(char * w) {
int sl = strlen(w), now = 1, mx = 0, mxp = 0;
for(register int i = 0; i < sl; ++i) {
int id = w[i] - 'a';
if(trie[now][id] && i - len[now] - 1 >= 0 && w[i - len[now] - 1] == w[i]) {
now = trie[now][id];
if(len[now] > mx)
mx = len[now], mxp = now;
}else {
int p = now;
while(p != 1 && (!trie[p][id] || i - len[p] - 1 < 0 || w[i - len[p] - 1] != w[i]))
p = fail[p];
if(trie[p][id]) {
now = trie[p][id];
if(len[now] > mx)
mx = len[now], mxp = now;
} else now = 1;
}
}
return mxp;
}
void print(int x) {
if(x == 0) return;
printf("%c", pid[x] + 'a');
if(fa[x] == 1) return;
print(fa[x]);
printf("%c", pid[x] + 'a');
}
}
int main() {
scanf("%s", s);
PAM::init(s);
PAM::create();
scanf("%s", word);
PAM::print(PAM::work(word));
return 0;
}
没有帐号? 立即注册