func_code_string: #include <bits/stdc++.h>   using namespace std;   const int dr[]{-1, -1, 0, 1, 1, 1, 0, -1};   const int dc[]{0, 1, 1, 1, 0, -1, -1, -1};   void run() {     ios::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);   }   const int sqrtQ = 150;   struct suffix_automaton {     struct state {       int len, link = 0, cnt = 0;       bool terminal = false, is_clone = false;       vector<int> nxt;       state(int len = 0) : len(len), nxt(26, -1) {}       bool have_next(char ch) { return nxt[ch -  a ] != -1; }       void clone(const state &other, int nlen) {         len = nlen;         nxt = other.nxt;         link = other.link;         is_clone = true;       }     };     vector<state> st;     int last = 0;     suffix_automaton() {       st.push_back(state());       st[0].link = -1;     }     suffix_automaton(const string &s) : suffix_automaton() {       for (char ch : s) extend(ch);       calc_number_of_occurrences();     }     void extend(char c) {       int cur = st.size();       st.push_back(state(st[last].len + 1));       st[cur].cnt = 1;       int p = last;       last = cur;       while (p != -1 && !st[p].have_next(c)) {         st[p].nxt[c -  a ] = cur;         p = st[p].link;       }       if (p == -1) return;       int q = st[p].nxt[c -  a ];       if (st[p].len + 1 == st[q].len) {         st[cur].link = q;         return;       }       int clone = st.size();       st.push_back(state());       st[clone].clone(st[q], st[p].len + 1);       while (p != -1 && st[p].nxt[c -  a ] == q) {         st[p].nxt[c -  a ] = clone;         p = st[p].link;       }       st[q].link = st[cur].link = clone;     }     void calc_number_of_occurrences() {       vector<vector<int>> lvl(st[last].len + 1);       for (int i = 1; i < st.size(); i++) lvl[st[i].len].push_back(i);       for (int i = st[last].len; i >= 0; i--)         for (auto cur : lvl[i]) st[st[cur].link].cnt += st[cur].cnt;     }     int count(const string &y) {       int cur = 0;       for (auto &it : y) {         if (!st[cur].have_next(it)) return 0;         cur = st[cur].nxt[it -  a ];       }       return st[cur].cnt;     }   } SA[(int)1e4];   string y;   vector<int> longestPrefix;   vector<int> Fail[26];   int fail(int k, char nxt) {     int &rt = Fail[nxt -  a ][k];     if (~rt) return rt;     while (k > 0 && y[k] != nxt) k = longestPrefix[k - 1];     if (nxt == y[k]) k++;     return rt = k;   }   void failure_function() {     int n = y.size();     longestPrefix = vector<int>(n);     for (int i = 0; i < 26; i++) Fail[i] = vector<int>(n + 1, -1);     for (int i = 1, k = 0; i < n; i++) longestPrefix[i] = k = fail(k, y[i]);   }   int main() {     run();     string s;     int q;     cin >> s >> q;     for (int i = 0; i < (int)(s.size()); i += sqrtQ)       SA[i / sqrtQ] = suffix_automaton(s.substr(i, sqrtQ));     auto solve = [&](int l, int r) {       int match = 0, cnt = 0;       for (int i = l; i <= r; i++) {         match = fail(match, s[i]);         if (match == (int)(y.size())) {           cnt++;           match = longestPrefix[match - 1];         }       }       return cnt;     };     while (q--) {       int t;       cin >> t;       if (t == 1) {         int idx;         char ch;         cin >> idx >> ch;         idx--;         s[idx] = ch;         SA[idx / sqrtQ] = suffix_automaton(s.substr(idx / sqrtQ * sqrtQ, sqrtQ));       } else {         int l, r;         cin >> l >> r >> y;         l--, r--;         failure_function();         if ((int)(y.size()) >= sqrtQ || r - l <= 2 * sqrtQ) {           cout << solve(l, r) <<   n ;           continue;         }         int ans = 0, len = (int)(y.size());         int st = l / sqrtQ, ed = r / sqrtQ;         for (int i = st + 1; i <= ed; i++)           ans += solve(max(l, i * sqrtQ - len + 1), min(r, i * sqrtQ + len - 2));         for (int i = st + 1; i < ed; i++) ans += SA[i].count(y);         ans += solve(l, (st + 1) * sqrtQ - 1);         ans += solve(ed * sqrtQ, r);         cout << ans <<   n ;       }     }   }   