func_code_string: #include <bits/stdc++.h>   using namespace std;   void task();   int main() {     srand(time(0));     ios_base::sync_with_stdio(0);     task();     return 0;   }   const int INF = 0x3f3f3f3f;   const int N = 1e6 + 10;   const int M = 1e5 + 10;   struct SufAutomaton {     struct State {       int len;       int link;       int cnt;       map<char, int> next;       State() : len(0), link(-1), cnt(0){};     };     State st[2 * N];     int sz = 1;     int last = 0;     void push(char ch) {       int cur = sz++;       st[cur].len = st[last].len + 1;       st[cur].cnt = 1;       int p = last;       last = cur;       for (; p != -1 && !st[p].next.count(ch); p = st[p].link)         st[p].next[ch] = cur;       if (p == -1) {         st[cur].link = 0;         return;       }       int q = st[p].next[ch];       if (st[p].len + 1 == st[q].len) {         st[cur].link = q;         return;       }       int clone = sz++;       st[clone].len = st[p].len + 1;       st[clone].next = st[q].next;       st[clone].link = st[q].link;       st[q].link = st[cur].link = clone;       for (; p != -1 && st[p].next.count(ch) && st[p].next[ch] == q;            p = st[p].link)         st[p].next[ch] = clone;     }     void calc() {       vector<pair<int, int> > v;       for (int i = 0; i < sz; ++i) v.push_back(pair<int, int>{st[i].len, i});       sort((v.begin()), (v.end()));       reverse((v.begin()), (v.end()));       for (pair<int, int> p : v) st[st[p.second].link].cnt += st[p.second].cnt;     }     int prefix_function(const string&& s) {       int n = s.length();       vector<int> p(n, 0);       for (int i = 1; i < n; ++i) {         int j = p[i - 1];         while (j && s[i] != s[j]) j = p[j - 1];         if (s[i] == s[j]) p[i] = j + 1;         if (p[i] == n / 2) return i;       }     }     int solve(string& s) {       int n = s.length();       int yet = prefix_function(s + s) - n;       int len = 0;       int ans = 0;       int cur = 0;       for (int i = 0; i < n; ++i) {         while (cur != -1 && st[cur].next.count(s[i]) == 0) {           cur = st[cur].link;           len = cur == -1 ? 0 : st[cur].len;         }         if (cur == -1) {           cur = 0;           len = 0;         } else {           ++len;           cur = st[cur].next[s[i]];         }       }       if (len == n) ans += st[cur].cnt;       for (int i = 0; i < yet; ++i) {         if (len == n) {           --len;           if (len <= st[st[cur].link].len) cur = st[cur].link;         }         while (cur != -1 && st[cur].next.count(s[i]) == 0) {           cur = st[cur].link;           len = cur == -1 ? 0 : st[cur].len;         }         if (cur == -1) {           cur = 0;           len = 0;         } else {           ++len;           cur = st[cur].next[s[i]];         }         if (len == n) {           ans += st[cur].cnt;         }       }       return ans;     }   };   string s;   SufAutomaton sa;   void task() {     cin >> s;     for (int i = 0; i < s.length(); ++i) sa.push(s[i]);     sa.calc();     int n;     cin >> n;     for (int i = 0; i < n; ++i) {       cin >> s;       cout << sa.solve(s) <<   n ;     }   }   