【BZOJ】【3676】【APIO2014】回文串

时间：2021-07-24 13:11:43

回文自动机/Manacher+SA

　　这道题可以用Manacher找出本质不同的回文串（令max增大的所有回文串），然后再用SA跑出来有多少相同。

　　还有一种做法就是回文自动机（Orz Hzwer）的裸题= =（hzwer的模板）

　　回文自动机的教程戳这里：http://blog.csdn.net/u013368721/article/details/42100363
　　

　　回文自动机：类似AC自动机的东西？我们处理回文子串是否相同的时候，很想用类似字典树的方式来存，但是由于是回文串= =所以不太方便用字典树上的一条链存整个回文串……那么我们可以只存回文串的一半！这样就可以实现在原串的基础上加一个字符来表示另一个回文串了！就可以 用字典树来表示了！再结合AC自动机……回文自动机就诞生啦= =（好吧其实还有其他不同）

　　当初写Manacher的做法的时候看了我写的是用KMP来跑有多少重复子串，果断T了= =然后去看了zyf的题解才知道可以用SA，但是同时也发现一个奇怪的问题：如果是能过这组数据：qbabqcfbabf 答案为6（bab*2）的做法，提交后会WA……我也不知道为什么（可能是我写的姿势不对？）QAQ求大神指教啊

 /**************************************************************

     Problem: 3676

     User: Tunix

     Language: C++

     Result: Accepted

     Time:804 ms

     Memory:35552 kb

 ****************************************************************/

 //BZOJ 3676

 #include<vector>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>'') {if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<='') {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 typedef long long LL;

 const int N=,INF=~0u>>;

 /*******************template********************/

 int n; LL ans=;

 char s[N];

 struct pam{

     int cnt, last;

     int a[N][],fail[N],l[N],size[N];

     pam(){

         cnt=;fail[]=fail[]=; l[]=-;

     }

     void Extend(int c,int n){

         int p=last;

         while(s[n-l[p]-]!=s[n]) p=fail[p];

         if (!a[p][c]){

             int now=++cnt,k=fail[p];

             l[now]=l[p]+;

             while(s[n-l[k]-]!=s[n]) k=fail[k];

             fail[now]=a[k][c]; a[p][c]=now;

         }

         last=a[p][c];

         size[last]++;

     }

     void solve(){

         D(i,cnt,){

             size[fail[i]]+=size[i];

             ans=max(ans,(LL)size[i]*l[i]);

         }

     }

 }pam;

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //  freopen("output.txt","w",stdout);

 #endif

     scanf("%s",s);

     n=strlen(s);

     rep(i,n) pam.Extend(s[i]-'a',i);

     pam.solve();

     printf("%lld\n",ans);

     return ;

 }

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 557  Solved: 184
[Submit][Status][Discuss]

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。

Input

输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。

Output

输出一个整数，为逝查回文子串的最大出现值。

Sample Input

【样例输入l】
abacaba

【样例输入2]
www

Sample Output

【样例输出l】
7

【样例输出2]
4

HINT

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。

在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：

● a出现4次，其出现值为4：1：1=4

● b出现2次，其出现值为2：1：1=2

● c出现1次，其出现值为l：1：l=l

● aba出现2次，其出现值为2：1：3=6

● aca出现1次，其出现值为1=1：3=3

●bacab出现1次，其出现值为1：1：5=5

● abacaba出现1次，其出现值为1：1：7=7

故最大回文子串出现值为7。

【数据规模与评分】

数据满足1≤字符串长度≤300000。

Source

[Submit][Status][Discuss]

相关文章