Codeforces 432D Prefixes and Suffixes kmp扩展操作,后缀数据结构

文章目录

题意题解 problem redive

题意

求字符串中每一个相等前后缀的长度以及其在全字符串中出现的次数.

题解

本题非常精妙. 首先思考求长度.可以使用kmp和哈希算法,但是哈希不能求出出现次数,因此被消灭了. 那考虑kmp解决第一个问题. kmp中的next数组表示的是全字符串的第i个前缀中前后缀的最大匹配长度. 对于全串来说,长度为$len$肯定是符合要求的,而$next[len]$必然也符合要求,同理$next[next[len]]$也是. 那么第一个问题已经解决了. 对于第二个问题,我们考虑一个符合条件的前缀$l$,且在以后的$l^{\prime },l^{\prime \prime }......$中存在$next[l^{\prime }]=l$,则我们构建一棵树,使$next[i]$是$i$的父亲,对所有$i$令$cnt[next[i]]+1$,则$dfs$统计$l$的子树之和,我们会发现所有$l$的前缀在后面出现的次数都被统计进去了.最终还少了第一个长度为$l$的前缀,答案**+1**即可. 本题使用后缀数据结构也可轻松通过.

const int yuzu=1e5; typedef int rize[yuzu|10]; typedef pair<int,int> pii; char s[yuzu|10]; rize pre,cnt; vector<pii> ans; vector<int> lj[yuzu|10]; void dfs(int u) { for (int v:lj[u]) dfs(v),cnt[u]+=cnt[v]; } int main() { int i,j,n; scanf("%s",s+1),n=strlen(s+1); for (*pre=j=-1,i=1;i<=n;++i) { for (;~j&&s[i]^s[j+1];j=pre[j]); pre[i]=++j,++cnt[j]; lj[j].push_back(i); } dfs(0); for (i=n;i;i=pre[i]) ans.push_back(pii(i,cnt[i]+1)); reverse(ans.begin(),ans.end()); printf("%d\n",ans.size()); for (pii i:ans) printf("%d %d\n",i.first,i.second); }

谢谢大家.