回文自动机入门题

URAL-1960.Palindromes and Super Abilities

•题意

　　给你一个长度为 n 的字符串 s，下标从 1 开始；

　　输出 n 个数，第 i 个数表示 1~i 内有多少个本质不同的回文串；

•题解

　　回文自动机入门题；

　　定义 ans[ i ] 表示 1~i 共有 $ans_{i}$ 个本质不同的回文串；

　　$ans_{i}=ans_{i-1}$+{第 i 个字符可形成本质不同的回文串 ? 1:0};

•Code

　　URAL1960.cpp

BZOJ-2565.最长双回文串

•题目描述

问题描述：
    顺序和逆序读起来完全一样的串叫做回文串。
    比如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|≤103。
　　对于30%的数据，2≤|S|≤104。
　　对于100%的数据，2≤|S|≤105。
时间限制：2秒

View Code

•题解

　　枚举位置 i，求出以第 i 个字符为结尾的最长的回文串长度 $x_i$ 和以第 i+1 个字符为开始的最长回文串长度 $y_{i+1}$；

　　最终答案为 $max{x_{i}+y_{i+1}}$;

　　正向跑一边回文自动机便可求出以第 i 个字符为结尾的最长回文串的长度；

　　反向跑一边回文自动机便可求出以第 i 个字符为开始的最长回文串的长度；

•Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+50;
 4 
 5 string s;
 6 
 7 ///a[0][i]:正向跑一边，求出以第i个字符为结尾的最长回文串的长度
 8 ///a[1][i]:反向跑一边，求出以第i个字符为开始的最长回文串的长度
 9 int a[2][maxn];
10 
11 struct PAM
12 {
13     int tot;
14     int last;
15     int len[maxn];
16     int fail[maxn];
17     int son[maxn][30];
18 
19     int newNode(int Len)
20     {
21         for(int i=0;i < 30;++i)
22             son[tot][i]=0;
23         len[tot]=Len;
24 
25         return tot++;
26     }
27     int getFail(int p,int i)
28     {
29         while(s[i-len[p]-1] != s[i])
30             p=fail[p];
31 
32         return p;
33     }
34     void Init()
35     {
36         tot=0;
37         last=0;
38 
39         newNode(0);
40         newNode(-1);
41 
42         fail[0]=1;
43     }
44 
45     void pam(int k)
46     {
47         Init();
48 
49 
50         for(int i=1;i < s.size();++i)
51         {
52             s[i]=s[i]-'a'+1;
53             int cur=getFail(last,i);
54 
55             if(!son[cur][s[i]])
56             {
57                 int now=newNode(len[cur]+2);
58                 fail[now]=son[getFail(fail[cur],i)][s[i]];
59                 son[cur][s[i]]=now;
60             }
61             last=son[cur][s[i]];
62 
63             a[k][i]=len[last];
64         }
65     }
66 }_pam;
67 int main()
68 {
69     cin>>s;
70     s.insert(0,"#");
71 
72     _pam.pam(0);
73     reverse(s.begin()+1,s.end());
74     _pam.pam(1);
75 
76     int ans=0;
77     int n=s.size()-1;
78     for(int i=1;i < n;++i)
79         ans=max(ans,a[0][i]+a[1][n-i]);
80 
81     printf("%d
",ans);
82 }

View Code