题目
给出一个字符串,从中找出两个不相交且长度和最大的非空回文子串,输出长度和。
2≤∣S∣≤2e5
input
abccbaa
output
7
解题思路
用马拉车没解出来,下午复习了下回文树,(自己没想出来suf[i]的最长回文子串怎么写🚮)尝试用xzh的思路。
既然回文树的len[i]已经处理出以i为结尾的最长回文子串长度,那么在insert的时候就可以据此求出每个前缀的最长回文子串长度,倒序处理字符串又可得出每个后缀的最长回文子串长度,这样就可以实现子串不相交然后去求答案。
注意回文树具体建树过程,自己写的时候wa了,还是对回文树理解的不够到位,欠灵活应用。
ac代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
int fail[maxn], len[maxn], nxt[maxn][30], s[maxn];
int last, n, p, maxlen;
char ss[maxn];
int maxpre[maxn];
int newnode(int l)//l: 节点p对应的最长回文子子串长度
{
for(int i = 0; i < 26; i++) nxt[p][i] = 0;
len[p] = l;
return p++;
}
void init()
{
memset(fail, 0, sizeof fail);
p = last = n = maxlen = 0, s[0] = -1;
newnode(0);//偶长度回文串
newnode(-1);//奇长度回文串
fail[0] = 1, fail[1] = 0;
}
int get_fail(int x)
{
while(s[n-len[x]-1]!=s[n]) x = fail[x];
return x;
}
void insert(int c, int type)//c=ch-'a'
{
s[++n] = c;
int cur = get_fail(last);//last=0, cur=1
if(!nxt[cur][c])
{
int now = newnode(len[cur]+2);
//初始cur=1, get_fail(fail[cur))=1, fail[now]=0
fail[now] = nxt[get_fail(fail[cur])][c];
nxt[cur][c] = now;
}
last = nxt[cur][c];
maxlen = max(maxlen, len[last]);
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
//abbaabbc
scanf("%s", ss+1);
int lenn = strlen(ss+1);
init();
for(int i = 1; i <= lenn; i++)
{
insert(ss[i]-'a', 0);
maxpre[i] = maxlen;
}
init();
int ans = 0;
for(int i = lenn; i > 1; i--)
{
insert(ss[i]-'a', 1);
ans = max(ans, maxpre[i-1]+maxlen);//min(i-1)=1
}
printf("%d\n", ans);
return 0;
}