bzoj 2565: 最长双回文串回文自动机

题目:

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数，表示最长双回文子串的长度。

题解:

首先我们有一个结论:(在WC2017被证明)

最长的双倍回文串中一定有一个回文串是不可拓展(最长的)的.

所以我们可以枚举取到最长的那个回文串,然后计算在剩下的字符中最长的回文串

设\(len_i\)表示终止在i上的最长的回文串的长度

那么所有的\(len\)可以使用后缀自动机线性求出.

这时答案就是所有的\(len_i + len_{i - len_i}\)中的最大值.

对吗 ??? ???

并不对,因为这样我们实际上只是默认右面的回文串是极大的.

并没有考虑左面的回文串取到最大值

所以我们还应该把串倒过来再做一次.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 100010;

struct PAM{

	struct Node{

		int nx[26];

		int len,fail,siz;

		Node(){

			memset(nx,0,sizeof nx);

			len = fail = siz = 0;

		}

	}T[maxn];

	int last,nodecnt,str[maxn],len;

	int mx[maxn];

	inline void init(){

		T[++nodecnt].len = -1;

		str[len=0] = -1;

		T[0].fail = 1;

	}

	PAM(){init();}

	inline void insert(char cha){

		int c = cha - 'a',p,cur,x;str[++len] = c;

		for(p = last;str[len - T[p].len - 1] != str[len];p = T[p].fail);

		if(T[p].nx[c] == 0){

			T[cur = ++ nodecnt].len = T[p].len + 2;

			for(x = T[p].fail;str[len - T[x].len - 1] != str[len];x = T[x].fail);

			T[cur].fail = T[x].nx[c];T[p].nx[c] = cur;

		}T[last = T[p].nx[c]].siz ++ ;

		mx[len] = T[last].len;

	}

}P1,P2;

char s[maxn];

int main(){

	scanf("%s",s+1);int n = strlen(s+1);

	for(int i=1;i<=n;++i) P1.insert(s[i]);

	for(int i=n;i>=1;--i) P2.insert(s[i]);

	int ans = 0;

	for(int i=1;i<=n;++i){

		ans = max(ans,P1.mx[i] + P1.mx[i - P1.mx[i]]);

		ans = max(ans,P2.mx[i] + P2.mx[i - P2.mx[i]]);

	}printf("%d\n",ans);

	getchar();getchar();

	return 0;

}

巴特西

bzoj 2565: 最长双回文串回文自动机

题目:

题解:

最新文章

热门文章

巴特西

bzoj 2565: 最长双回文串 回文自动机

题目:

题解:

最新文章

热门文章

bzoj 2565: 最长双回文串回文自动机