「BZOJ3676」[Apio2014] 回文串
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。
题解
用manacher找出本质不同的回文串，每个串在后缀自动机上查询出现次数
本质不同的回文串是能使mx增长的回文串
查询出现次数可以用倍增找出对应结点
刚A完就被人D飞了：“写什么马拉车+自动机”
然后就补了个回文自动机。。。
见 http://blog.csdn.net/u013368721/article/details/42100363。。。
然后此题是裸题
sam+manacher
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int bin[20]; int n,p[300005]; char ch[300005]; struct sam{ int last,cnt; int fa[600005],a[600005][26],mx[600005],size[600005]; int v[300005],q[600005],pos[600005],dep[600005],an[600005][19]; sam(){ last=++cnt; } void extend(int c,int id){ int p=last,np=last=++cnt;mx[np]=mx[p]+1; size[np]=1;pos[id]=last; while(p&&!a[p][c])a[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else { int q=a[p][c]; if(mx[p]+1==mx[q])fa[np]=q; else { int nq=++cnt;mx[nq]=mx[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=fa[p]; } } } void pre(){ for(int i=1;i<=cnt;i++)v[mx[i]]++; for(int i=1;i<=n;i++)v[i]+=v[i-1]; for(int i=cnt;i;i--)q[v[mx[i]]--]=i; for(int i=cnt;i;i--) { int t=q[i]; size[fa[t]]+=size[t]; } for(int i=1;i<=cnt;i++) { int t=q[i]; dep[t]=dep[fa[t]]+1; an[t][0]=fa[t]; for(int j=1;bin[j]<=dep[t];j++) an[t][j]=an[an[t][j-1]][j-1]; } } void query(int l,int r){ int mid=pos[r]; for(int i=18;i>=0;i--) { int t=an[mid][i]; if(mx[t]>=r-l+1)mid=t; } ans=max(ans,(ll)size[mid]*(r-l+1)); } }sam; void manacher() { int mx=0,id; for(int i=1;i<=n;i++) { if(mx>i)p[i]=min(mx-i,p[2*id-i-1]); else p[i]=0; while(ch[i+p[i]+1]==ch[i-p[i]]) { p[i]++; sam.query(i-p[i]+1,i+p[i]); } if(p[i]+i>mx)mx=p[i]+i,id=i; } mx=0; for(int i=1;i<=n;i++) { if(mx>i)p[i]=min(mx-i-1,p[2*id-i]); else {p[i]=1;sam.query(i-p[i]+1,i+p[i]-1);} while(ch[i+p[i]]==ch[i-p[i]]) { p[i]++; sam.query(i-p[i]+1,i+p[i]-1); } if(p[i]+i>mx)mx=p[i]+i,id=i; } } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;i++)sam.extend(ch[i]-'a',i); sam.pre(); ch[0]='+';ch[n+1]='*'; manacher(); printf("%lld\n",ans); return 0; } |
pam
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int n; char ch[300005]; struct pam{ int cnt,last; int a[300005][26],fa[300005],l[300005],size[300005]; pam(){ cnt=1;fa[0]=fa[1]=1;l[1]=-1; } void extend(int c,int n){ int p=last; while(ch[n-l[p]-1]!=ch[n])p=fa[p]; if(!a[p][c]) { int now=++cnt,k=fa[p]; l[now]=l[p]+2; while(ch[n-l[k]-1]!=ch[n])k=fa[k]; fa[now]=a[k][c];a[p][c]=now; } last=a[p][c]; size[last]++; } void solve(){ for(int i=cnt;i;i--) { size[fa[i]]+=size[i]; ans=max(ans,(ll)size[i]*l[i]); } } }pam; int main() { scanf("%s",ch+1); n=strlen(ch+1); for(int i=1;i<=n;i++) pam.extend(ch[i]-'a',i); pam.solve(); printf("%lld\n",ans); return 0; } |
计数器 9785144
OI 课件=>
OI 课件=>
[…] 「BZOJ3676」[Apio2014] 回文串 – 后缀自动… […]
黄学长，你的manacher有些问题
两个for里面都应该
if(mx>i)p[i]=min(mx-i,p[2*id-i]);实测AC，跑得更快
并且就能过掉楼下的hack数据
为什么马拉车字符串之间没有添其他符号啊
马拉车部分好像是有些问题的
学长你的马拉车+sam算法有些问题dtddtddtddtddtddtddtddtddtddtddfddtddtddtddtdftddttdtddtddfddtddtddtddtddtddtddtddtddtddtddttdtdd
这组应该187,代码跑的192
学长求教为什么要倍增啊QAQ
parent树上倍增要查询什么呢QAQ
在parent树上找对应结点
嗯。。就是不用在自动机上跑一遍就可以找到它的位置是么QAQ
是
嗯嗯谢谢学长，麻烦学长了
求教回文自动机
求教回文自动机QAQ
求问：对于数据qbabqcfbabf，答案应该是6吧（bab*2）？而不是应该是5……？
是6啊。。。
回文自动机的做法……
是啊。。。
QAQ那应该是我写的姿势不对……我学您的写法写的回文自动机AC了……但是跑出来是5……sorry麻烦您了