首页 > 代码库 > codeforces 432D Prefixes and Suffixes
codeforces 432D Prefixes and Suffixes
由于包含了前缀与后缀,很容易想到用KMP去算前缀与后缀的公共缀。另外要计算某个后缀在整个串中出现的次数,由于后缀自动机是比较容易求的,然后就直接上后缀自动机了。先分别用KMP算法与后缀自动机跑一遍,然后对后缀自动机做一个拓扑排序,根据拓扑结构更新一遍每个串出现的次数就可以了。然后直接沿着KMP的next数组以及后缀自动机节点的父亲边走就可以了。
代码如下:
#include <stdio.h>#include <string.h>const int maxn = 100100;struct sanode{ sanode *f, *ch[26]; int l, m; sanode(){ f = 0; memset(ch, 0, sizeof(ch)); l = 0, m = 1; } void init(){ f = 0; memset(ch, 0, sizeof(ch)); l = 0, m = 1; } }sam[maxn*2], *b[maxn*2];int cnt[maxn], tot;sanode *tail, *s;char str[maxn];int f[maxn]; //KMPstruct resultSet{ int l, m;}res[maxn];void addSuffix(int c, int len){ sanode *p = tail, *np = &sam[++tot]; np->init(); tail = np; np->l = len; for(;p&&!p->ch[c];p=p->f) p->ch[c] = np; if(!p) np->f = s; else{ if(p->ch[c]->l == p->l + 1) np->f = p->ch[c]; else{ sanode * q = p->ch[c], *r = &sam[++tot]; *r = *q; r->l = p->l + 1; r->m = 0; q->f = np->f = r; for(;p && p->ch[c]==q; p=p->f) p->ch[c] = r; } }}void topSortSuffix(int len){ for(int i = 0; i <= tot; i ++) cnt[sam[i].l] ++; for(int i = 1; i <= len; i ++) cnt[i] += cnt[i-1]; for(int i = 0; i <= tot; i ++) b[--cnt[sam[i].l]] = &sam[i]; for(int i = tot; i > 0; i --){ b[i]->f->m += b[i]->m; }}void KMP(){ int c = 0; for(int i = 2; str[i]; i ++){ while(c && str[c+1] != str[i]) c = f[c]; if(str[c+1] == str[i]) f[i] = ++c; }}int main(){ int len = 0; s = tail = &sam[tot = 0]; s->init(); scanf("%s", str+1); for(len = 1; str[len]; len ++){ addSuffix(str[len] - ‘A‘, len); } len --; topSortSuffix(len); KMP(); sanode *p = tail; int number = 0; for(; len; len = f[len]){ while(p && p->l > len) p = p->f; if(!p) break; if(p->l == len){ res[number].l = len; res[number].m = p->m; number ++; } } printf("%d\n", number); for(int i = number - 1; i >= 0; i --) printf("%d %d\n", res[i].l , res[i].m); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。