题意
给定一个长度为(n)的母串
(q)组询问
这个串可以旋转(就是把最后一位丢到最前面这样子)
问这个串以及其旋转的串在给定的串中出现了多少次
Sol
旋转就把它复制一遍接在后面
然后就在(sam)上匹配
跳(parent)树的父亲到最后一个长度大于等于询问串长
然后统计(size)
防止重复算,就标记一下这个点是否算过
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
const int maxn(2e6 + 5);
int len[maxn], trans[26][maxn], fa[maxn], tot = 1, last = 1;
int n, q, id[maxn], t[maxn], size[maxn], vis[maxn];
char s[maxn];
IL void Extend(RG int c){
RG int p = last, np = ++tot;
len[last = np] = len[p] + 1, size[np] = 1;
while(p && !trans[c][p]) trans[c][p] = np, p = fa[p];
if(!p) fa[np] = 1;
else{
RG int q = trans[c][p];
if(len[q] == len[p] + 1) fa[np] = q;
else{
RG int nq = ++tot;
fa[nq] = fa[q], len[nq] = len[p] + 1;
for(RG int i = 0; i < 26; ++i) trans[i][nq] = trans[i][q];
fa[np] = fa[q] = nq;
while(p && trans[c][p] == q) trans[c][p] = nq, p = fa[p];
}
}
}
int main(){
scanf(" %s", s), n = strlen(s);
for(RG int i = 0; i < n; ++i) Extend(s[i] - 'a');
for(RG int i = 1; i <= tot; ++i) ++t[len[i]];
for(RG int i = 1; i <= tot; ++i) t[i] += t[i - 1];
for(RG int i = 1; i <= tot; ++i) id[t[len[i]]--] = i;
for(RG int i = tot; i; --i) size[fa[id[i]]] += size[id[i]];
q = Input();
for(RG int i = 1, l, tl; i <= q; ++i){
scanf(" %s", s + 1), l = strlen(s + 1);
for(RG int j = 1; j < l; ++j) s[j + l] = s[j];
RG ll ans = 0; tl = l + l;
for(RG int j = 1, nw = 1, cnt = 0; j < tl; ++j){
while(nw && !trans[s[j] - 'a'][nw]) nw = fa[nw], cnt = len[nw];
if(!nw) nw = 1, cnt = 0;
else ++cnt, nw = trans[s[j] - 'a'][nw];
while(nw && len[fa[nw]] >= l) nw = fa[nw], cnt = len[nw];
if(cnt >= l && vis[nw] != i) ans += size[nw], vis[nw] = i;
}
printf("%lld
", ans);
}
return 0;
}