Aho-Corasick - DP Applications

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Count strings of length n over alphabet 'a'..('a'+K-1)
5
// that avoid a set of forbidden patterns (and also how many contain at least one).
6
// DP state includes: (AC node, matchedFlag).
7
// Complexity: O(n * S * K)
8
9
struct AhoCorasick {
10
    int K; // alphabet size
11
    vector<vector<int>> next; // transitions (filled to be total)
12
    vector<int> link;         // failure links
13
    vector<int> out;          // 1 if this node (or suffix) matches any pattern
14
15
    AhoCorasick(int K): K(K) {
16
        add_node(); // root = 0
17
    }
18
19
    int add_node() {
20
        next.push_back(vector<int>(K, -1));
21
        link.push_back(0);
22
        out.push_back(0);
23
        return (int)next.size()-1;
24
    }
25
26
    void insert(const string &s) {
27
        int v = 0;
28
        for (char ch : s) {
29
            int c = ch - 'a';
30
            if (next[v][c] == -1) next[v][c] = add_node();
31
            v = next[v][c];
32
        }
33
        out[v] = 1; // mark terminal
34
    }
35
36
    void build() {
37
        queue<int> q;
38
        // Initialize root transitions
39
        for (int c = 0; c < K; ++c) {
40
            int u = next[0][c];
41
            if (u != -1) {
42
                link[u] = 0;
43
                q.push(u);
44
            } else {
45
                next[0][c] = 0; // complete missing transitions to root
46
            }
47
        }
48
        // BFS
49
        while (!q.empty()) {
50
            int v = q.front(); q.pop();
51
            out[v] = out[v] || out[link[v]]; // inherit terminality
52
            for (int c = 0; c < K; ++c) {
53
                int u = next[v][c];
54
                if (u != -1) {
55
                    link[u] = next[link[v]][c];
56
                    q.push(u);
57
                } else {
58
                    next[v][c] = next[link[v]][c]; // fill to total function
59
                }
60
            }
61
        }
62
    }
63
};
64
65
int main() {
66
    ios::sync_with_stdio(false);
67
    cin.tie(nullptr);
68
69
    const long long MOD = 1000000007LL;
70
71
    // Example setup
72
    int K = 2; // alphabet = {'a','b'}
73
    vector<string> patterns = {"ab", "baa"};
74
    long long n = 10; // length
75
76
    AhoCorasick ac(K);
77
    for (auto &p : patterns) ac.insert(p);
78
    ac.build();
79
80
    int S = (int)ac.next.size();
81
82
    // dp0[u] = count of length-t strings ending at node u with no match so far
83
    // dp1[u] = count of length-t strings ending at node u with at least one match so far
84
    vector<long long> dp0(S, 0), dp1(S, 0), ndp0(S, 0), ndp1(S, 0);
85
    dp0[0] = 1; // start at root, length 0
86
87
    for (long long t = 0; t < n; ++t) {
88
        fill(ndp0.begin(), ndp0.end(), 0);
89
        fill(ndp1.begin(), ndp1.end(), 0);
90
        for (int u = 0; u < S; ++u) {
91
            long long a0 = dp0[u];
92
            long long a1 = dp1[u];
93
            if ((a0 | a1) == 0) continue;
94
            for (int c = 0; c < K; ++c) {
95
                int v = ac.next[u][c];
96
                if (!ac.out[v]) {
97
                    // stay unmatched if we were unmatched
98
                    ndp0[v] = (ndp0[v] + a0) % MOD;
99
                } else {
100
                    // crossing into terminal by this char turns matched on
101
                    ndp1[v] = (ndp1[v] + a0) % MOD;
102
                }
103
                // once matched, always matched
104
                ndp1[v] = (ndp1[v] + a1) % MOD;
105
            }
106
        }
107
        dp0.swap(ndp0);
108
        dp1.swap(ndp1);
109
    }
110
111
    long long avoid = 0, matched = 0, total0 = 1;
112
    for (int u = 0; u < S; ++u) if (!ac.out[u]) avoid = (avoid + dp0[u]) % MOD;
113
    for (int u = 0; u < S; ++u) matched = (matched + dp1[u]) % MOD;
114
    for (long long i = 0; i < n; ++i) total0 = (total0 * K) % MOD; // total strings k^n
115
116
    cout << "Avoiders: " << avoid << "\n";
117
    cout << "Contain >=1 forbidden: " << matched << "\n";
118
    cout << "Check k^n: " << total0 << " and avoid+match mod M = " << (avoid + matched) % MOD << "\n";
119
120
    return 0;
121
}
122

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Build AC, compress to safe states, add one aggregator state for "already matched",
5
// and compute counts for length n via matrix exponentiation.
6
7
struct AhoCorasick {
8
    int K;
9
    vector<vector<int>> next;
10
    vector<int> link;
11
    vector<int> out;
12
    AhoCorasick(int K): K(K) { add_node(); }
13
    int add_node(){ next.push_back(vector<int>(K,-1)); link.push_back(0); out.push_back(0); return (int)next.size()-1; }
14
    void insert(const string &s){ int v=0; for(char ch: s){ int c=ch-'a'; if(next[v][c]==-1) next[v][c]=add_node(); v=next[v][c]; } out[v]=1; }
15
    void build(){ queue<int> q; for(int c=0;c<K;c++){ int u=next[0][c]; if(u!=-1){ link[u]=0; q.push(u);} else next[0][c]=0; } while(!q.empty()){ int v=q.front(); q.pop(); out[v]|=out[link[v]]; for(int c=0;c<K;c++){ int u=next[v][c]; if(u!=-1){ link[u]=next[link[v]][c]; q.push(u);} else next[v][c]=next[link[v]][c]; } } }
16
};
17
18
struct Matrix {
19
    int n; long long MOD; vector<vector<long long>> a; // a[i][j]
20
    Matrix(int n=0, long long MOD=1000000007LL): n(n), MOD(MOD), a(n, vector<long long>(n,0)) {}
21
    static Matrix identity(int n, long long MOD){ Matrix I(n, MOD); for(int i=0;i<n;i++) I.a[i][i]=1; return I; }
22
    Matrix operator*(const Matrix& o) const {
23
        Matrix r(n, MOD);
24
        // naive O(n^3); consider optimizing if sparse
25
        for(int i=0;i<n;i++){
26
            for(int k=0;k<n;k++) if(a[i][k]){
27
                long long aik = a[i][k];
28
                for(int j=0;j<n;j++) if(o.a[k][j]){
29
                    r.a[i][j] = (r.a[i][j] + aik * o.a[k][j]) % MOD;
30
                }
31
            }
32
        }
33
        return r;
34
    }
35
};
36
37
Matrix mpow(Matrix base, unsigned long long e){
38
    Matrix res = Matrix::identity(base.n, base.MOD);
39
    while(e){
40
        if(e & 1ULL) res = res * base;
41
        base = base * base;
42
        e >>= 1ULL;
43
    }
44
    return res;
45
}
46
47
int main(){
48
    ios::sync_with_stdio(false);
49
    cin.tie(nullptr);
50
51
    const long long MOD = 1000000007LL;
52
    int K = 3; // alphabet {'a','b','c'}
53
    vector<string> patterns = {"ab", "ba", "caa"};
54
    unsigned long long n = 1000000000000ULL; // 1e12
55
56
    AhoCorasick ac(K);
57
    for (auto &p: patterns) ac.insert(p);
58
    ac.build();
59
60
    int N = (int)ac.next.size();
61
    vector<int> safe_idx(N, -1);
62
    vector<int> id2node; id2node.reserve(N);
63
    for(int u=0; u<N; ++u){ if(!ac.out[u]){ safe_idx[u] = (int)id2node.size(); id2node.push_back(u); } }
64
    int S = (int)id2node.size();
65
66
    // Dimension: S safe states + 1 aggregator (last index)
67
    int D = S + 1, AGG = S;
68
    Matrix M(D, MOD);
69
70
    // Column-vector convention: v_next = M * v_curr
71
    // Fill transitions from safe states
72
    for(int j=0; j<S; ++j){
73
        int u = id2node[j];
74
        for(int c=0;c<K;c++){
75
            int v = ac.next[u][c];
76
            if(!ac.out[v]){
77
                int i = safe_idx[v];
78
                M.a[i][j] = (M.a[i][j] + 1) % MOD; // safe->safe
79
            } else {
80
                M.a[AGG][j] = (M.a[AGG][j] + 1) % MOD; // safe->aggregator
81
            }
82
        }
83
    }
84
    // Aggregator self-loop: once matched, every next char keeps you matched; k choices each step
85
    M.a[AGG][AGG] = (M.a[AGG][AGG] + K) % MOD;
86
87
    // Initial vector v0: start at root (if safe)
88
    vector<long long> v0(D, 0);
89
    if (safe_idx[0] == -1) {
90
        // Root is terminal (rare unless empty pattern). Then all length>=1 are matched immediately.
91
        v0[AGG] = 1;
92
    } else {
93
        v0[safe_idx[0]] = 1;
94
    }
95
96
    Matrix P = mpow(M, n);
97
98
    // v_n = P * v0
99
    vector<long long> vn(D, 0);
100
    for(int i=0;i<D;i++){
101
        long long sum = 0;
102
        for(int j=0;j<D;j++) if(P.a[i][j] && v0[j]){
103
            sum = (sum + P.a[i][j] * v0[j]) % MOD;
104
        }
105
        vn[i] = sum;
106
    }
107
108
    long long avoid = 0;
109
    for(int i=0;i<S;i++) avoid = (avoid + vn[i]) % MOD;
110
    long long matched = vn[AGG];
111
112
    cout << "Avoiders (mod 1e9+7): " << avoid << "\n";
113
    cout << "Contain >=1 forbidden (mod 1e9+7): " << matched << "\n";
114
115
    return 0;
116
}
117

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given: at position i, only a subset of letters is allowed.
5
// Count strings of length n that avoid forbidden patterns.
6
7
struct AhoCorasick {
8
    int K;
9
    vector<vector<int>> next;
10
    vector<int> link;
11
    vector<int> out;
12
    AhoCorasick(int K): K(K){ add_node(); }
13
    int add_node(){ next.push_back(vector<int>(K,-1)); link.push_back(0); out.push_back(0); return (int)next.size()-1; }
14
    void insert(const string &s){ int v=0; for(char ch: s){ int c=ch-'a'; if(next[v][c]==-1) next[v][c]=add_node(); v=next[v][c]; } out[v]=1; }
15
    void build(){ queue<int> q; for(int c=0;c<K;c++){ int u=next[0][c]; if(u!=-1){ link[u]=0; q.push(u);} else next[0][c]=0; } while(!q.empty()){ int v=q.front(); q.pop(); out[v]|=out[link[v]]; for(int c=0;c<K;c++){ int u=next[v][c]; if(u!=-1){ link[u]=next[link[v]][c]; q.push(u);} else next[v][c]=next[link[v]][c]; } } }
16
};
17
18
int main(){
19
    ios::sync_with_stdio(false);
20
    cin.tie(nullptr);
21
22
    const long long MOD = 1000000007LL;
23
24
    int K = 4; // alphabet: {'a','b','c','d'}
25
    vector<string> patterns = {"ab", "bcd"};
26
    int n = 8;
27
28
    // allowed[i] is a bitmask over K letters indicating which are allowed at position i
29
    vector<int> allowed(n, 0);
30
    // Example: alternate constraints: positions even allow {a,c}, odd allow {b,d}
31
    for(int i=0;i<n;i++){
32
        if(i%2==0) allowed[i] = (1<<0) | (1<<2); // a,c
33
        else allowed[i] = (1<<1) | (1<<3);       // b, d
34
    }
35
36
    AhoCorasick ac(K);
37
    for(auto &p: patterns) ac.insert(p);
38
    ac.build();
39
40
    int S = (int)ac.next.size();
41
    vector<long long> dp(S, 0), ndp(S, 0);
42
    dp[0] = 1;
43
44
    for(int i=0;i<n;i++){
45
        fill(ndp.begin(), ndp.end(), 0);
46
        for(int u=0; u<S; ++u){
47
            if (dp[u] == 0) continue;
48
            if (ac.out[u]) continue; // never continue from terminal states
49
            for(int c=0;c<K;c++) if(allowed[i] & (1<<c)){
50
                int v = ac.next[u][c];
51
                if (!ac.out[v]){
52
                    ndp[v] += dp[u];
53
                    if (ndp[v] >= MOD) ndp[v] -= MOD;
54
                }
55
                // transitions into terminal states are skipped (avoidance)
56
            }
57
        }
58
        dp.swap(ndp);
59
    }
60
61
    long long ans = 0;
62
    for(int u=0; u<S; ++u) if(!ac.out[u]){ ans += dp[u]; if(ans >= MOD) ans -= MOD; }
63
64
    cout << "Avoiders with position constraints: " << ans << "\n";
65
    return 0;
66
}
67