首页 > 代码库 > codeforces 432D Prefixes and Suffixes

codeforces 432D Prefixes and Suffixes

2024-07-15 08:07:54   213人阅读

由于包含了前缀与后缀，很容易想到用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;}

 


联系
我们