A1280. 最長雙回文串 時間限制: 2.0s 記憶體限制: 512.0MB 總送出次數: 349 AC次數: 171 平均分: 65.67 将本題分享到: 檢視未格式化的試題 送出 試題讨論 試題來源 中國國家隊清華集訓 2011-2012 第二天 問題描述 順序和逆序讀起來完全一樣的串叫做回文串。比如acbca是回文串,而abc不是(abc的順序為“abc”,逆序為“cba”,不相同)。
輸入長度為n的串S,求S的最長雙回文子串T,即可将T分為兩部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。 輸入格式 一行由小寫英文字母組成的字元串S。 輸出格式 一行一個整數,表示最長雙回文子串的長度。 樣例輸入 baacaabbacabb 樣例輸出 12 樣例說明 從第二個字元開始的字元串aacaabbacabb可分為aacaa與bbacabb兩部分,且兩者都是回文串。 資料規模及限制 對于10%的資料,2≤|S|≤10 3。
對于30%的資料,2≤|S|≤10 4。
對于100%的資料,2≤|S|≤10 5。
時間限制:2秒
回文樹先入個門
更詳細的見部落格 http://blog.csdn.net/u013368721/article/details/42100363
/*======================================================
# Author: whai
#
# Last modified: 2015-10-05 15:37
#
# Filename: tsinsen_A1280.cpp
======================================================*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
using namespace std;
#define LL __int64
#define PB push_back
#define P pair<int, int>
#define X first
#define Y second
const int N = 1e5 + 5;
const int M = 26;
struct PalTree {
int nxt[N][M]; //表示編号為i的節點表示的回文串在兩邊添加字元c以後變成的回文串的編号
int fail[N]; //表示節點i失配以後跳轉不等于自身的節點i表示的回文串的最長字尾回文串
int cnt[N]; //表示節點i表示的本質不同的串的個數(建樹時求出的不是完全的,最後count()函數跑一遍以後才是正确的)
int num[N]; //表示以節點i表示的最長回文串的最右端點為回文串結尾的回文串個數
int len[N]; //表示編号為i的節點表示的回文串的長度(一個節點表示一個回文串)
int S[N];
int last, n, p;
int new_node(int x) {
memset(nxt[p], 0, sizeof(nxt[p]));
cnt[p] = 0;
num[p] = 0;
len[p] = x;
return p++;
}
void init() {
p = 0;
new_node(0);
new_node(-1);
last = 0;
n = 0;
S[n] = -1;
fail[0] = 1;
}
int get_fail(int x) {
while(S[n - len[x] - 1] != S[n]) x = fail[x];
return x;
}
int add(int x) {
x -= 'a';
S[++n] = x;
int cur = get_fail(last);
if(!nxt[cur][x]) {
int now = new_node(len[cur] + 2);
fail[now] = nxt[get_fail(fail[cur])][x];
nxt[cur][x] = now;
num[now] = num[fail[now]] + 1;
}
last = nxt[cur][x];
++cnt[last];
return len[last];
}
void count() {
for(int i = p - 1; i >= 0; --i)
cnt[fail[i]] += cnt[i];
}
};
PalTree pt;
int len[N];
char str[N];
void gao(char str[]) {
int ans = 0;
int n = strlen(str);
pt.init();
for(int i = n - 1; i >= 0; --i) {
len[i] = pt.add(str[i]);
}
pt.init();
for(int i = 0; i < n - 1; ++i) {
ans = max(ans, pt.add(str[i]) + len[i + 1]);
}
printf("%d\n", ans);
}
int main() {
while(scanf("%s", str) != EOF) {
gao(str);
}
return 0;
}