hdu 4436 str2int（字尾自動機）

題目連結：hdu 4436 str2int

解題思路

将所有字元串拼接在一起，連接配接處用不會出現的字元10代替。然後根據拓撲序，維護每個節點的sum 取模後的和，cnt 以該節點為終止位置的字元串個數。

代碼

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = ;
const int SIGMA_SIZE = ;
const int mod = ;

struct SAM {
    int sz, last;
    int g[maxn<<][SIGMA_SIZE], pre[maxn<<], step[maxn<<];


    void newNode (int s) {
        step[++sz] = s;
        pre[sz] = ;
        memset(g[sz], , sizeof(g[sz]));
    }

    void init () {
        sz = , last = ;
        newNode();
    }

    void insert(int v) {
        newNode(step[last] + );
        int p = last, np = sz;

        while (p && !g[p][v]) {
            g[p][v] = np;
            p = pre[p];
        }

        if (p) {
            int q = g[p][v];
            if (step[q] == step[p] + )
                pre[np] = q;
            else {
                newNode(step[p] + );
                int nq = sz;
                for (int j = ; j < SIGMA_SIZE; j++) g[nq][j] = g[q][j];

                pre[nq] = pre[q];
                pre[np] = pre[q] = nq;

                while (p && g[p][v] == q) {
                    g[p][v] = nq;
                    p = pre[p];
                }
            }
        } else
            pre[np] = ;
        last = np;
    }

    int cnt[maxn<<], sum[maxn<<], du[maxn<<];

    int solve () {
        int ret = ;
        for (int i = ; i <= sz; i++)
            cnt[i] = sum[i] = du[i] = ;

        for (int i = ; i <= sz; i++) {
            for (int j = ; j < SIGMA_SIZE; j++)
                du[g[i][j]]++;
        }

        queue<int> que;
        que.push();
        cnt[] = ;

        while (!que.empty()) {
            int u = que.front();
            que.pop();

            ret = (ret + sum[u]) % mod;

            for (int i = ; i < SIGMA_SIZE; i++) {
                int v = g[u][i];

                du[v]--;
                if (du[v] ==  && v) que.push(v);

                if (v ==  || (i ==  && u == )) continue;
                if (i == ) continue;
                cnt[v] = (cnt[u] + cnt[v]) % mod;
                sum[v] = (sum[v] + sum[u] *  % mod + cnt[u] * i % mod) % mod;
            }
        }
        return ret;
    }
}SA;

int N;
char str[maxn];

int main () {
    while (scanf("%d", &N) == ) {
        SA.init();
        while (N--) {
            scanf("%s", str);
            int n = strlen(str);
            for (int i = ; i < n; i++) SA.insert(str[i] - '0');
            SA.insert();
        }
        printf("%d\n", SA.solve());
    }
    return ;
}