思路与算法

用AC自动机识别禁串，传播bad后只保留从根经安全边可达的状态。对安全图求SCC。若循环SCC中某点有不止一条内部字符边，则答案无穷；否则每个循环SCC是一条简单环。缩点DAG若有路径经过至少三个循环SCC，也无穷。其余情况下计所有纯周期环，以及从一个循环SCC经无环状态到另一个循环SCC的路径数。

正确性说明

分支强连通结构允许反复选择不同闭游走，产生无限多个模平移后仍不同的双向串。三个循环依次可达时，中间循环可停留任意圈，亦产生无限种。没有这些情形时，双向无限游走两端只能在简单环上，且中间没有第三个循环；它唯一归类为一个纯环或一条有向过渡路径。有限记忆的AC状态由字符后缀决定，计数没有额外状态歧义。

复杂度

设Trie状态V、字母数t≤6。建自动机、可达性、SCC、缩点和拓扑计数共O(tV+输入总长)时间，O(tV)空间，数组初始化同阶。

易错点

先删不可达状态，否则会误判无穷。不同字符形成的平行缩点边分别计数。循环节点接收的路径计入答案后向外以1作为新起点，不能把经过第三个环的路径混入有限计数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    array<int, 6> go;
    int fail = 0;
    bool bad = false;
    Node() {
        go.fill(0);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t, n;
    cin >> t >> n;
    vector<Node> a(1);
    while (n--) {
        string s;
        cin >> s;
        int u = 0;
        for (char c : s) {
            int z = c - 'a';
            if (!a[u].go[z]) {
                a[u].go[z] = a.size();
                a.emplace_back();
            }
            u = a[u].go[z];
        }
        a[u].bad = true;
    }
    queue<int> q;
    for (int c = 0; c < t; c++)
        if (a[0].go[c])
            q.push(a[0].go[c]);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        a[u].bad |= a[a[u].fail].bad;
        for (int c = 0; c < t; c++) {
            int v = a[u].go[c];
            if (v) {
                a[v].fail = a[a[u].fail].go[c];
                q.push(v);
            } else
                a[u].go[c] = a[a[u].fail].go[c];
        }
    }
    vector<int> reach(a.size());
    queue<int> rq;
    reach[0] = 1;
    rq.push(0);
    while (!rq.empty()) {
        int u = rq.front();
        rq.pop();
        for (int c = 0; c < t; c++) {
            int v = a[u].go[c];
            if (!a[v].bad && !reach[v]) {
                reach[v] = 1;
                rq.push(v);
            }
        }
    }
    vector<int> id(a.size(), -1);
    int N = 0;
    for (int i = 0; i < (int)a.size(); i++)
        if (!a[i].bad && reach[i])
            id[i] = N++;
    vector<vector<int>> g(N), h(N);
    for (int i = 0; i < (int)a.size(); i++)
        if (id[i] >= 0)
            for (int c = 0; c < t; c++)
                if (id[a[i].go[c]] >= 0) {
                    int u = id[i], v = id[a[i].go[c]];
                    g[u].push_back(v);
                    h[v].push_back(u);
                }
    vector<int> vis(N), ord;
    for (int s = 0; s < N; s++)
        if (!vis[s]) {
            vector<pair<int, int>> st(1, {s, 0});
            vis[s] = 1;
            while (!st.empty()) {
                int u = st.back().first, &k = st.back().second;
                if (k == (int)g[u].size()) {
                    ord.push_back(u);
                    st.pop_back();
                } else {
                    int v = g[u][k++];
                    if (!vis[v]) {
                        vis[v] = 1;
                        st.push_back({v, 0});
                    }
                }
            }
        }
    vector<int> comp(N, -1), size;
    for (int j = N - 1; j >= 0; j--) {
        int s = ord[j];
        if (comp[s] >= 0)
            continue;
        int c = size.size(), sz = 0;
        vector<int> st(1, s);
        comp[s] = c;
        while (!st.empty()) {
            int u = st.back();
            st.pop_back();
            sz++;
            for (int v : h[u])
                if (comp[v] < 0) {
                    comp[v] = c;
                    st.push_back(v);
                }
        }
        size.push_back(sz);
    }
    int M = size.size();
    vector<int> cyc(M), deg(M);
    vector<vector<int>> dag(M);
    for (int u = 0; u < N; u++) {
        int internal = 0;
        for (int v : g[u])
            if (comp[u] == comp[v])
                internal++;
            else {
                dag[comp[u]].push_back(comp[v]);
                deg[comp[v]]++;
            }
        if (size[comp[u]] > 1 || internal) {
            cyc[comp[u]] = 1;
            if (internal != 1) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }
    vector<int> depth = cyc;
    vector<long long> dp(M);
    long long ans = accumulate(cyc.begin(), cyc.end(), 0LL);
    for (int i = 0; i < M; i++)
        if (!deg[i])
            q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (depth[u] >= 3) {
            cout << -1 << '\n';
            return 0;
        }
        if (cyc[u]) {
            ans += dp[u];
            dp[u] = 1;
        }
        for (int v : dag[u]) {
            depth[v] = max(depth[v], depth[u] + cyc[v]);
            dp[v] = min(2147483648LL, dp[v] + dp[u]);
            if (!--deg[v])
                q.push(v);
        }
    }
    cout << ans << '\n';
}