# CF235C Cyclical Quest

### 题目描述

Some days ago, WJMZBMR learned how to answer the query "how many times does a string $x$ occur in a string $s$ " quickly by preprocessing the string $s$ . But now he wants to make it harder.

So he wants to ask "how many consecutive substrings of $s$ are cyclical isomorphic to a given string $x$ ". You are given string $s$ and $n$ strings $x_{i}$ , for each string $x_{i}$ find, how many consecutive substrings of $s$ are cyclical isomorphic to $x_{i}$ .

Two strings are called cyclical isomorphic if one can rotate one string to get the other one. 'Rotate' here means 'to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order'. For example, string "abcde" can be rotated to string "deabc". We can take characters "abc" from the beginning and put them at the end of "de".

### 输入格式

The first line contains a non-empty string $s$ . The length of string $s$ is not greater than $10^{6}$ characters.

The second line contains an integer $n$ ( $1<=n<=10^{5}$ ) — the number of queries. Then $n$ lines follow: the $i$ -th line contains the string $x_{i}$ — the string for the $i$ -th query. The total length of $x_{i}$ is less than or equal to $10^{6}$ characters.

In this problem, strings only consist of lowercase English letters.

### 输出格式

For each query $x_{i}$ print a single integer that shows how many consecutive substrings of $s$ are cyclical isomorphic to $x_{i}$ . Print the answers to the queries in the order they are given in the input.

### 样例输入

baabaabaaa
5
a
ba
baa
aabaa
aaba


### 样例输出

7
5
7
3
5


### 代码

#include <bits/stdc++.h>

const int N = 1e6+50;
const int SIZ = N << 1;

struct Sam {
int top, last;
int ch[SIZ][26], fa[SIZ], mx[SIZ], rcnt[SIZ];
int buc[N], id[SIZ];

Sam(): top(1), last(1) {}

void extend(char c) {
int x = c - 'a', p = last;
int np = last = ++top;
mx[np] = mx[p] + 1;
rcnt[np] = 1;
for (; p && !ch[p][x]; p = fa[p])
ch[p][x] = np;
if (!p) {
fa[np] = 1;
return;
}
int q = ch[p][x];
if (mx[q] == mx[p] + 1) {
fa[np] = q;
return;
}
int nq = ++top;
mx[nq] = mx[p] + 1;
fa[nq] = fa[q];
fa[q] = fa[np] = nq;
memcpy(ch[nq], ch[q], sizeof ch[nq]);
for (; ch[p][x] == q; p = fa[p])
ch[p][x] = nq;
}

void work() {
for (int i = 1; i <= top; i++)
buc[mx[i]]++;
for (int i = 1; i <= top; i++)
buc[i] += buc[i-1];
for (int i = 1; i <= top; i++)
id[buc[mx[i]]--] = i;

for (int i = top; i >= 2; i--) {
int u = id[i];
rcnt[fa[u]] += rcnt[u];
}
}
} sam;

char s[N], p[N<<1];
int vis[SIZ];

int main() {
scanf("%s", s);
int n = strlen(s), m;
for (int i = 0; i < n; i++)
sam.extend(s[i]);
sam.work();

scanf("%d", &m);
for (int cas = 1; cas <= m; cas++) {
scanf("%s", p);
int lp = strlen(p);
memcpy(p+lp, p, lp-1);
int u = 1, len = 0, ans = 0;
for (int i = 0; i < lp*2-1; i++) {
int x = p[i] - 'a';
if (sam.ch[u][x]) {
u = sam.ch[u][x];
len++;
} else {
while (len && !sam.ch[u][x]) {
u = sam.fa[u];
len = sam.mx[u];
}
if (sam.ch[u][x]) {
u = sam.ch[u][x];
len++;
}
}
while (sam.mx[sam.fa[u]] >= lp) {
u = sam.fa[u];
len = sam.mx[u];
}
if (len >= lp && vis[u] != cas) {
vis[u] = cas;
ans += sam.rcnt[u];
}
}
printf("%d\n", ans);
}
return 0;
}


暂无评论