1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

struct SuffixAutomaton {
    struct State {
        int len, link;
        map<char, int> next;
    };
    vector<State> st;
    vector<int> cnt;
    int last;

    SuffixAutomaton(int n) {
        st.reserve(2 * n);
        cnt.assign(2 * n, 0);
        st.push_back({0, -1});
        last = 0;
    }

    void extend(char c) {
        int cur = st.size();
        st.push_back({st[last].len + 1, -1});
        cnt.push_back(1);
        
        int p = last;
        while (p != -1 && !st[p].next.count(c)) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = st.size();
                st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
                cnt.push_back(0);
            }
        }
        last = cur;
    }

    void countSubstrings() {
        vector<int> order(st.size());
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {
            return st[a].len > st[b].len;
        });
        for (int v : order) {
            if (st[v].link != -1) cnt[st[v].link] += cnt[v];
        }
    }

    int getDuplicateCount() {
        int result = 0;
        for (int i = 1; i < st.size(); ++i) {
            if (cnt[i] > 1) result = (result + 1) % MOD;
        }
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    SuffixAutomaton sam(n);
    for (char c : s) sam.extend(c);
    sam.countSubstrings();
    cout << sam.getDuplicateCount() << "\n";

    while (q--) {
        int p;
        char c;
        cin >> p >> c;
        --p;
        s[p] = c;
        sam = SuffixAutomaton(n);
        for (char c : s) sam.extend(c);
        sam.countSubstrings();
        cout << sam.getDuplicateCount() << "\n";
    }

    return 0;
}