海亮01/08字符串
T1
题意
给定一个主串\(S\)和\(n\)个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。
题解
如果不问循环同构,只问正常询问串的出现次数,会吗?
直接上板子即可对叭?
那么对于循环同构,我们可以直接加长一倍(加到 \(2n-1\),如果是 \(2n\) 就有一个重复了),那么新串所有长度为 \(n\) 的子串就可以代表所有循环同构。
然后对这样一个新串进行询问,每次添加一个字符找到最长的有这个字符转移的状态,同时更新当前已查找的子串长度。
然后如果现在已查找的子串长度超过 \(n\) 怎么办?直接暴力跳 \(link\) 树直到当前节点的长度区间包含 \(n\)。然后统计次数。
同时为了解决重复计数的问题,查询之后给这个状态打个标记,下次不统计即可,然后别忘了一个询问做完了清空标记。
Accept=Happy New Year! 好评
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e6 + 10;
char ch[maxn];
bool book[maxn * 2];
struct SAM{
struct node{
int link, len, siz;
unordered_map<char,int> nxt;
}d[maxn * 2];
int a[maxn * 2], cf[maxn], tot, last;
void build(){tot = last = 0;d[0].link = -1;}
void insert(char ch){
int cur = ++tot;d[cur].siz = 1;
d[cur].len = d[last].len + 1;
int p = last;
while(p != -1 && !d[p].nxt[ch]){d[p].nxt[ch] = cur;p = d[p].link;}
if(p == -1){d[cur].link = 0;}
else{
int q = d[p].nxt[ch];
if(d[p].len + 1 == d[q].len){d[cur].link = q;}
else{
int clone = ++tot;
d[clone].link = d[q].link;
d[clone].nxt = d[q].nxt;
d[clone].len = d[p].len + 1;
while(p != -1 && d[p].nxt[ch] == q){d[p].nxt[ch] = clone;p = d[p].link;}
d[q].link = d[cur].link = clone;
}
}
last = cur;
}
void build(char *s){
build();
int len = strlen(s + 1);
for(int i = 1;i <= len;i++)insert(s[i]);
for(int i = 0;i <= tot;i++)cf[d[i].len]++;cf[0] = 0;
for(int i = 1;i <= len;i++)cf[i] += cf[i - 1];
for(int i = 0;i <= tot;i++)a[cf[d[i].len]--] = i;
for(int i = tot;i;i--){int p = a[i];d[d[p].link].siz += d[p].siz;}
}
int query(char *s){
int ans = 0;
int p = 0, len = strlen(s + 1), dep = 0;
vector<int> vec;vec.clear();
for(int i = 1;i < len * 2;i++){
char ch = s[(i - 1) % len + 1];
while(p != -1 && !d[p].nxt[ch]){p = d[p].link;dep = d[p].len;}
if(p != -1){
p = d[p].nxt[ch];dep++;
while(dep > len){dep--;if(dep <= d[d[p].link].len)p = d[p].link;}
if(dep >= len && !book[p]){ans += d[p].siz;book[p] = 1;vec.push_back(p);}
}
else p = 0;
}
for(int u : vec)book[u] = false;
return ans;
}
}sam;
signed main(){
scanf("%s",ch + 1);sam.build(ch);
for(int T = read();T;T--){
scanf("%s",ch + 1);
printf("%d\n",sam.query(ch));
}
return 0;
}