E. Three strings 广义后缀自动机

http://codeforces.com/problemset/problem/452/E

多个主串的模型。

建立一个广义后缀自动机，可以dp出每个状态的endpos集合大小。同时也维护一个R[]表示那个串出现过。

所以可以算出每个状态的dp[i][k]表示第k个串在第i个状态中出现的次数。

可以知道sigma dp[i][0...k]是等于 endpos集合的大小。

然后把这个贡献加到min(i)....max(i)中去就可以了

差分一下。

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int MOD = 1e9 + ;

const int maxn = 6e5 + , N = ;

struct Node {

    int mxCnt; //mxCnt表示后缀自动机中当前节点识别子串的最大长度

    int miCnt; //miCnt表示后缀自动机中当前节点识别子串的最小长度

    int id; //表示它是第几个后缀自动机节点，指向了它，但是不知道是第几个，用id判断

    int pos; //pos表示它在原串中的位置。

    bool flag; //表示当前节点是否能识别前缀

    bool R[]; // 广义后缀自动机识别此状态是否在第R[i]个主串中出现过

    struct Node *pNext[N], *fa;

}suffixAutomaton[maxn], *root, *last; //大小需要开2倍，因为有一些虚拟节点

int t;  //用到第几个节点

struct Node *create(int mxCnt = -, struct Node *node = NULL) { //新的节点

    if (mxCnt != -) {

        suffixAutomaton[t].mxCnt = mxCnt, suffixAutomaton[t].fa = NULL;

        for (int i = ; i < N; ++i) suffixAutomaton[t].pNext[i] = NULL;

    } else {

        suffixAutomaton[t] = *node; //保留了node节点所有的指向信息。★全部等于node

        //可能需要注意下pos，在原串中的位置。现在pos等于原来node的pos

    }

    suffixAutomaton[t].id = t;  //必须要有的，不然id错误

    suffixAutomaton[t].flag = false; //默认不是前缀节点

    return &suffixAutomaton[t++];

}

void addChar(int x, int pos, int id) { //pos表示在原串的位置

    struct Node *p = last;

    if (p->pNext[x] != NULL) { // 有了，就不需要np，广义后缀自动机

        struct Node *q = p->pNext[x];

        if (p->mxCnt +  == q->mxCnt) {

            last = q; //用来接收后缀字符

            q->flag = true;

            q->R[id] = true;

            return;

        }

        //现在的q没办法成为接受后缀的点

        //那么就开一个节点模拟它，所以这个节点是id的前缀节点

        struct Node * nq = create(-, q);

        for (int i = ; i < ; ++i) nq->R[i] = false;

        nq->mxCnt = p->mxCnt + ;

        nq->R[id] = true;

        nq->flag = true; //这个点是属于id的。是id的前缀节点，因为q不能接受后缀

        q->fa = nq; //这里是没有np的

        q->miCnt = nq->mxCnt + ;

        for (; p && p->pNext[x] == q; p = p->fa) p->pNext[x] = nq;

        last = nq; //成为接受后缀的节点。

        return;

    }

    struct Node *np = create(p->mxCnt + , NULL);

    for (int i = ; i < ; ++i) np->R[i] = false; //每次都要清空

    np->R[id] = true;

    np->flag = true; //前缀节点

    np->pos = pos, last = np; //last是最尾那个可接收后缀字符的点。

    for (; p != NULL && p->pNext[x] == NULL; p = p->fa) p->pNext[x] = np;

    if (p == NULL) {

        np->fa = root;

        np->miCnt = ; // 从根节点引一条边过来

        return;

    }

    struct Node *q = p->pNext[x];

    if (q->mxCnt == p->mxCnt + ) { //中间没有任何字符，可以用来代替接受后缀、

        np->fa = q;

        np->miCnt = q->mxCnt + ; // q是状态8的"ab"，np是状态7的"bab"长度是2+1

        return;

    }

    struct Node *nq = create(-, q); // 新的q节点，用来代替q，帮助np接收后缀字符

    for (int i = ; i < ; ++i) nq->R[i] = false;

    nq->mxCnt = p->mxCnt + ; //就是需要这样，这样中间不包含任何字符

    q->miCnt = nq->mxCnt + , np->miCnt = nq->mxCnt + ;

    q->fa = nq, np->fa = nq; //现在nq是包含了本来q的所有指向信息

    for (; p && p->pNext[x] == q; p = p->fa) {

        p->pNext[x] = nq;

    }

}

void init() {

    t = ;

    root = last = create(, NULL);

}

char str[maxn];

LL dp[maxn][];

queue<int> que;

int in[maxn];

LL ans[maxn];

void work() {

    init();

    int len = inf;

    for (int i = ; i < ; ++i) {

        last = root;

        scanf("%s", str + );

        int t = ;

        for (int j = ; str[j]; ++j) {

            t++;

            addChar(str[j] - 'a', j, i);

        }

        len = min(len, t);

    }

    for (int i = ; i < t; ++i) {

        in[suffixAutomaton[i].fa->id]++;

//        if (suffixAutomaton[i].flag) {

            for (int j = ; j < ; ++j) {

                dp[i][j] = suffixAutomaton[i].R[j];

            }

//        }

    }

    for (int i = ; i < t; ++i) {

        if (in[i] == ) {

            que.push(i);

        }

    }

    while (!que.empty()) {

        int cur = que.front();

        que.pop();

        if (!cur) break;

        for (int i = ; i < ; ++i) {

            dp[suffixAutomaton[cur].fa->id][i] += dp[cur][i];

        }

        in[suffixAutomaton[cur].fa->id]--;

        if (in[suffixAutomaton[cur].fa->id] == ) que.push(suffixAutomaton[cur].fa->id);

    }

    for (int i = ; i < t; ++i) {

        LL res = ;

        for (int j = ; j < ; ++j) {

            res = res * dp[i][j] % MOD;

        }

//        printf("%lld ", res);

        int en = suffixAutomaton[i].mxCnt;

        int be = suffixAutomaton[i].miCnt;

        ans[en + ] = (ans[en + ] - res + MOD) % MOD;

        ans[be] = (ans[be] + res) % MOD;

    }

//    printf("\n");

    for (int i = ; i <= len; ++i) {

        ans[i] = (ans[i] + ans[i - ] + MOD) % MOD;

    }

    for (int i = ; i <= len; ++i) {

        printf("%I64d ", ans[i]);

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn = 3e5 + , N = ;

const int MOD = 1e9 + ;

struct SAM {

    int mxCnt[maxn << ], son[maxn << ][N], fa[maxn << ], pos[maxn << ];

    int flag[maxn << ][]; //是否前缀节点

    int root, last, DFN, t;

    int create() {

        ++t;

        mxCnt[t] = pos[t] = fa[t] = NULL;

        for (int i = ; i < ; ++i) flag[t][i] = NULL;

        for (int i = ; i < N; ++i) son[t][i] = NULL;

        return t;

    }

    void init() {

        DFN = ;

        ++DFN;

        t = , root = ;

        last = create();

    }

    void addChar(int x, int _pos, int id) { // _pos表示在原串中的位置

        int p = last;

        if (son[p][x]) { //已经存在，广义后缀自动机

            int q = son[p][x];

            if (mxCnt[p] +  == mxCnt[q]) {

                last = q;

                flag[q][id] = DFN;

                return;

            }

            int nq = create();

            for (int i = ; i < N; ++i) son[nq][i] = son[q][i];

            fa[nq] = fa[q];

            pos[nq] = pos[q];

            mxCnt[nq] = mxCnt[p] + ;

            flag[nq][id] = DFN;

            fa[q] = nq;

            for (; p && son[p][x] == q; p = fa[p]) son[p][x] = nq;

            last = nq;

            return;

        }

        int np = create();

        last = np;

        mxCnt[np] = mxCnt[p] + , pos[np] = _pos, flag[np][id] = DFN; //前缀节点

        for (; p && son[p][x] == NULL; p = fa[p]) son[p][x] = np;

        if (p == NULL) {

            fa[np] = root;

            return;

        }

        int q = son[p][x];

        if (mxCnt[q] == mxCnt[p] + ) {

            fa[np] = q;

            return;

        }

        int nq = create(); //用来代替q的，默认不是前缀节点

        flag[nq][id] = DFN - ; //默认不是前缀节点

        pos[nq] = pos[q]; //pos要和q相同

        for (int i = ; i < N; ++i) son[nq][i] = son[q][i];

        fa[nq] = fa[q], mxCnt[nq] = mxCnt[p] + ;

        fa[q] = nq, fa[np] = nq;

        for (; p && son[p][x] == q; p = fa[p]) son[p][x] = nq;

    }

    int dp[maxn << ][], in[maxn << ], que[maxn << ];

    void topo() { //多次使用不用清空

        int head = , tail = ;

        for (int i = ; i <= t; ++i) {

            for (int j = ; j < ; ++j) {

                dp[i][j] = flag[i][j] == DFN;

            }

            in[fa[i]]++;

        }

        for (int i = ; i <= t; ++i) {

            if (in[i] == ) que[tail++] = i;

        }

        while (head < tail) {

            int cur = que[head++];

            if (cur == root) break;

            for (int i = ; i < ; ++i) dp[fa[cur]][i] += dp[cur][i];

            in[fa[cur]]--;

            if (in[fa[cur]] == ) que[tail++] = fa[cur];

        }

    }

} sam;

char str[maxn], sub[maxn];

LL ans[maxn << ];

void work() {

    int len = inf;

    sam.init();

    for (int i = ; i < ; ++i) {

        sam.last = sam.root;

        scanf("%s", str + );

        int t = strlen(str + );

        len = min(len, t);

        for (int j = ; str[j]; ++j) {

            sam.addChar(str[j] - 'a', j, i);

        }

    }

    sam.topo();

    for (int i = ; i <= sam.t; ++i) {

        LL res = ;

        for (int j = ; j < ; ++j) {

            res = res * sam.dp[i][j] % MOD;

//            printf("%d ", sam.dp[i][j]);

        }

//        printf("\n");

        ans[sam.mxCnt[sam.fa[i]] + ] = (ans[sam.mxCnt[sam.fa[i]] + ] + res) % MOD;

        ans[sam.mxCnt[i] + ] = (ans[sam.mxCnt[i] + ] - res + MOD) % MOD;

    }

    for (int i = ; i <= len; ++i) ans[i] = (ans[i] + ans[i - ] + MOD) % MOD;

    for (int i = ; i <= len; ++i) {

        printf("%I64d ", ans[i]);

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

也可以直接sam，把三个串加入到sam中，中间用特殊符号分割

然后dp[i][j]表示到达第i个状态，能得到的j号串的个数是多少即可

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn = 3e5 + , N = ;

struct SAM {

    int mxCnt[maxn << ], son[maxn << ][N], fa[maxn << ], pos[maxn << ];

//    int flag[maxn << 1][3]; //是否前缀节点

    int flag[maxn << ][];

    int root, last, DFN, t;

    int create() {

        ++t;

        mxCnt[t] = pos[t] = fa[t] = NULL;

        for (int i = ; i < N; ++i) son[t][i] = NULL;

        return t;

    }

    void init() {

        ++DFN;

        t = , root = ;

        last = create();

    }

    void addChar(int x, int _pos, int id) { // _pos表示在原串中的位置

        int p = last;

        int np = create();

        last = np;

        mxCnt[np] = mxCnt[p] + , pos[np] =  << _pos; //前缀节点

        flag[np][id] = DFN;

        for (; p && son[p][x] == NULL; p = fa[p]) son[p][x] = np;

        if (p == NULL) {

            fa[np] = root;

            return;

        }

        int q = son[p][x];

        if (mxCnt[q] == mxCnt[p] + ) {

            fa[np] = q;

            return;

        }

        int nq = create(); //用来代替q的，默认不是前缀节点

        pos[nq] = pos[q]; //pos要和q相同

        for (int i = ; i < N; ++i) son[nq][i] = son[q][i];

        fa[nq] = fa[q], mxCnt[nq] = mxCnt[p] + ;

        fa[q] = nq, fa[np] = nq;

        for (; p && son[p][x] == q; p = fa[p]) son[p][x] = nq;

    }

    int dp[maxn << ][], in[maxn << ], que[maxn << ];

    void topo() {

        for (int i = ; i <= t; ++i) {

            in[fa[i]]++;

            for (int j = ; j < ; ++j) {

                dp[i][j] = flag[i][j] == DFN;

            }

        }

        int head = , tail = ;

        for (int i = ; i <= t; ++i) {

            if (in[i] == ) que[tail++] = i;

        }

        while (head < tail) {

            int cur = que[head++];

            if (cur == root) break;

            pos[fa[cur]] |= pos[cur];

            for (int j = ; j < ; ++j) {

                dp[fa[cur]][j] += dp[cur][j];

            }

            in[fa[cur]]--;

            if (in[fa[cur]] == ) que[tail++] = fa[cur];

        }

    }

} sam;

char str[maxn];

LL ans[maxn];

const int MOD = 1e9 + ;

void work() {

    sam.init();

    int len = inf;

    for (int i = ; i < ; ++i) {

        scanf("%s", str + );

        int t = ;

        for (int j = ; str[j]; ++j) {

            t++;

            sam.addChar(str[j] - 'a', i, i);

        }

        len = min(len, t);

        sam.addChar(, , );

    }

    sam.topo();

    for (int i = ; i <= sam.t; ++i) {

        if (sam.pos[i] != ) continue;

        LL res = ;

        for (int j = ; j < ; ++j) {

            res = res * sam.dp[i][j] % MOD;

        }

        int be = sam.mxCnt[sam.fa[i]] + ;

        int en = sam.mxCnt[i];

        ans[be] = (ans[be] + res) % MOD;

        ans[en + ] = (ans[en + ] - res + MOD) % MOD;

    }

    for (int i = ; i <= len; ++i) ans[i] = (ans[i] + ans[i - ] + MOD) % MOD;

    for (int i = ; i <= len; ++i) {

        printf("%lld ", ans[i]);

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

E. Three strings 广义后缀自动机

最新文章

热门文章