首页 > 代码库 > 2565: 最长双回文串 - BZOJ

2565: 最长双回文串 - BZOJ

2024-07-06 06:11:35   225人阅读

Description

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

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

Output

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

baacaabbacabb

Sample Output

12

HINT

样例说明

　　从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

数据规模及限制

　　对于10%的数据，2≤|S|≤10^3。

　　对于30%的数据，2≤|S|≤10^4。

　　对于100%的数据，2≤|S|≤10^5。

 

其实很简单

我们先用manacher算法求出以每个点为中心的最长回文串

然后求出l[i]和r[i]，分别表示向前和向后的最远的 回文串能覆盖到i 的中心（当然i是manacher算法里面加入的‘#’）因为只有这个才可以做分割点

 1 const
 2     maxn=200200;
 3 var
 4     c:array[0..maxn]of char;
 5     p,ll,rr:array[0..maxn]of longint;
 6     n:longint;
 7 
 8 function min(x,y:longint):longint;
 9 begin
10     if x<y then exit(x);
11     exit(y);
12 end;
13 
14 function max(x,y:longint):longint;
15 begin
16     if x>y then exit(x);
17     exit(y);
18 end;
19 
20 procedure init;
21 var
22     i,id,r:longint;
23 begin
24     n:=1;
25     while not eoln do
26       begin
27         inc(n);
28         read(c[n]);
29         inc(n);
30       end;
31     c[0]:=‘$‘;
32     c[n+1]:=‘#‘;
33     id:=0;
34     r:=0;
35     for i:=1 to n do
36       begin
37         if r>=i then p[i]:=min(p[id<<1-i],r-i+1)
38         else p[i]:=1;
39         while c[i+p[i]]=c[i-p[i]] do
40           inc(p[i]);
41         if i+p[i]-1>r then
42         begin
43           id:=i;
44           r:=i+p[i]-1;
45         end;
46       end;
47 end;
48 
49 procedure work;
50 var
51     i,k,ans:longint;
52 begin
53     k:=1;
54     for i:=1 to n do
55       if i and 1=1 then
56       begin
57         while k+p[k]-1<i do
58           inc(k);
59         ll[i]:=i-k;
60       end;
61     k:=n;
62     for i:=n downto 1 do
63       if i and 1=1 then
64       begin
65         while k-p[k]+1>i do
66           dec(k);
67         rr[i]:=k-i;
68       end;
69     ans:=0;
70     for i:=1 to n do
71       if i and 1=1 then ans:=max(ans,ll[i]+rr[i]);
72     writeln(ans);
73 end;
74 
75 begin
76     init;
77     work;
78 end.
View Code

 


联系
我们