回文自动机/Manacher+SA

---

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

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

　　回文自动机的教程戳这里：

　　

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

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

1 /************************************************************** 2     Problem: 3676 3     User: Tunix 4     Language: C++ 5     Result: Accepted 6     Time:804 ms 7     Memory:35552 kb 8 ****************************************************************/ 9  10 //BZOJ 367611 #include
      
       12 #include
       
        13 #include
        
         14 #include
         
          15 #include
          
           16 #include
           
            17 #define rep(i,n) for(int i=0;i
            
             =n;--i)20 using namespace std;21 22 int getint(){23 int v=0,sign=1; char ch=getchar();24 while(ch<'0'||ch>'9') { if (ch=='-') sign=-1; ch=getchar();}25 while(ch>='0'&&ch<='9') {v=v*10+ch-'0'; ch=getchar();}26 return v*sign;27 }28 typedef long long LL;29 const int N=300010,INF=~0u>>2;30 /*******************template********************/31 int n; LL ans=0;32 char s[N];33 struct pam{34 int cnt, last;35 int a[N][26],fail[N],l[N],size[N];36 pam(){37 cnt=1;fail[0]=fail[1]=1; l[1]=-1;38 }39 void Extend(int c,int n){40 int p=last;41 while(s[n-l[p]-1]!=s[n]) p=fail[p];42 if (!a[p][c]){43 int now=++cnt,k=fail[p];44 l[now]=l[p]+2;45 while(s[n-l[k]-1]!=s[n]) k=fail[k];46 fail[now]=a[k][c]; a[p][c]=now;47 }48 last=a[p][c];49 size[last]++;50 }51 void solve(){52 D(i,cnt,1){53 size[fail[i]]+=size[i];54 ans=max(ans,(LL)size[i]*l[i]);55 }56 }57 }pam;58 int main(){59 #ifndef ONLINE_JUDGE60 freopen("input.txt","r",stdin);61 // freopen("output.txt","w",stdout);62 #endif63 scanf("%s",s);64 n=strlen(s);65 rep(i,n) pam.Extend(s[i]-'a',i);66 pam.solve();67 printf("%lld\n",ans);68 return 0;69 }
            
           
          
         
        
       
      

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 557  Solved: 184

[][][]

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

[ ][ ][ ]