- #include#include#include#include#include using namespace std;#define lc x << 1#define rc x << 1 | 1#define mid((l + r) >> 1)#define lson lc,
- l,
- mid#define rson rc,
- mid + 1,
- r const int N = 2e6 + 5;
- typedef long long ll;
- int n,
- ri[N];
- char s[N];
- struct node {
- int ch[26],
- par,
- val;
- }
- t[N];
- int sz = 1,
- root = 1,
- last = 1;
- void extend(int c) {
- int p = last,
- np = ++sz;
- t[np].val = t[p].val + 1;
- ri[np]++;
- for (; p && !t[p].ch[c]; p = t[p].par) t[p].ch[c] = np;
- if (!p) t[np].par = root;
- else {
- int q = t[p].ch[c];
- if (t[q].val == t[p].val + 1) t[np].par = q;
- else {
- int nq = ++sz;
- t[nq] = t[q];
- t[nq].val = t[p].val + 1;
- t[q].par = t[np].par = nq;
- for (; p && t[p].ch[c] == q; p = t[p].par) t[p].ch[c] = nq;
- }
- }
- last = np;
- }
- int vis[N];
- void walk(int id) { //puts("walk");
- int u = root,
- len = n + n - 1,
- ans = 0,
- nowLen = 0;
- for (int i = 1; i <= len; i++) {
- int c = s[i] - 'a';
- if (t[u].ch[c]) u = t[u].ch[c],
- nowLen++;
- else {
- while (u && !t[u].ch[c]) u = t[u].par;
- if (!u) u = root,
- nowLen = 0;
- else nowLen = t[u].val + 1,
- u = t[u].ch[c];
- }
- //printf("i %d %d %d %d\n",i,c,u,nowLen);
- if (vis[u] != id && nowLen >= n) vis[u] = id,
- ans += ri[u]; //,printf("ans %d %d\n",u,ri[u]);
- if (n != 1) while (t[t[u].par].val + 1 >= n) u = t[u].par,
- nowLen = t[u].val;
- //printf("nowu %d\n",u);
- }
- printf("%d\n", ans);
- }
- int c[N],
- a[N];
- void RadixSort() {
- for (int i = 1; i <= sz; i++) c[t[i].val]++;
- for (int i = 1; i <= n; i++) c[i] += c[i - 1];
- for (int i = sz; i >= 1; i--) a[c[t[i].val]--] = i;
- }
- void solve() {
- RadixSort();
- int u;
- for (int i = sz; i >= 1; i--) u = a[i],
- ri[t[u].par] += ri[u];
- int m;
- scanf("%d", &m);
- for (int i = 1; i <= m; i++) {
- scanf("%s", s + 1);
- n = strlen(s + 1);
- for (int i = 1; is[i]; walk(i);
- }
- }
- int main() {
- //freopen("in","r",stdin);
- scanf("%s", s + 1);
- n = strlen(s + 1);
- for (int i = 1; i <= n; i++) extend(s[i] - 'a');
- solve();
- }
来源: