【BZOJ 3676】 3676: [Apio2014]回文串（SAM+Manacher+倍增）-白红宇

【BZOJ 3676】 3676: [Apio2014]回文串（SAM+Manacher+倍增）

阅读量：5025 次

发布时间：2019-06-12

本文共 2046 字，大约阅读时间需要 6 分钟。

3676: [Apio2014]回文串

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 2343 Solved: 1031

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

【分析】

　　听说回文自动机可以秒掉这题，以后再学吧。

　　用串建SAM，然后求出right数组。

　　manacher告诉我们，本质不同的回文串最多n个，只有在mx变的时候可能增加一个回文串。

　　用manacher求出所有本质不同的回文串，然后在SAM上问。

　　那就是问[L,R]这个区间的子串出现了多少次【感觉这个用后缀数组的话是nlogn^2的

　　从SAM的pre边相当于AC自动机上的fail，形成一棵树，pre树上倍增即可。

　　就是从POS[R]开始跳，当他代表的子串的长度大于r-l+1，即可计入答案，当然子串长度越小越好（更有可能出现最多次）

　　【记得拓扑序

　　【啊。。。卡空间。。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 #define Maxn 301000  8 #define LL long long  9  10 // int mymax(int x,int y) {return x>y?x:y;} 11 LL mymax(LL x,LL y) {
    return x>y?x:y;} 12 int mymin(int x,int y) {
    return x
           
            =1;i--) q[v[t[i].step]--]=i; 74 75 for(int i=tot;i>=1;i--) 76 { 77 int nw=q[i]; 78 t[t[nw].pre].rt+=t[nw].rt; 79 } 80 } 81 void ffind(int l,int r) 82 { 83 l=l/2+1;r=(r+1)/2; 84 int x=pos[r]; 85 for(int i=18;i>=0;i--) 86 { 87 if(t[ff[x][i]].step>=r-l+1) x=ff[x][i]; 88 } 89 ans=mymax(ans,1LL*(r-l+1)*t[x].rt); 90 } 91 }sam; 92 93 char s[Maxn]; 94 // int a[2*Maxn],p[2*Maxn]; 95 96 void manacher(int l) 97 { 98 v[0]=99; 99 for(int i=0;i
            
             =0)108 {109 q[i]++;110 sam.ffind(i-q[i]+1,i+q[i]-1);111 }112 if(i+q[i]-1>mx) mx=i+q[i]-1,id=i;113 }114 }115 116 int main()117 {118 scanf("%s",s);119 int l=strlen(s);120 last=tot=1;now=0;121 for(int i=0;i