题意
给定一个主串 \(S\) 和 \(n\) 个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。
分析
后缀自动机好题。
循环同构的过程可以看作从该串的头部删除一个字符,并在尾部加入一个字符。
在后缀自动机上,跳 parent 树的过程就相当于删除头部的若干个字符。
所以我们可以套路地把询问串 \(s_i\) 复制一遍首尾相接,然后模拟 SAM 匹配子串的过程,有以下两种情况:
- 如果无法继续匹配,那么跳 parent 树直至可以匹配并更新长度。
- 如果长度 \(l\) 大于该询问串的长度,删除首字母并更新当前长度,同时跳 parent 树找到当前节点。
另外一个问题是循环同构可能产生相同的子串,比如 \(\texttt{abab}\) 将前两位拼到最后得到的字符串也是 \(\texttt{abab}\)。
此时就要在节点上存储一个标记,判断该子串有没有被访问过。
也可以使用哈希等方法求出最小循环节再处理。
时间复杂度 \(O(|S|+\sum|s_i|)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000006
namespace SAM
{
struct node
{
int fa, len, ch[26];
node() {memset(this, 0, sizeof *this);}
}st[maxn<<1];
int siz[maxn<<1];
int la=1, cnt=1;
void insert(int c)
{
int p=la, u=la=++cnt;
siz[u]=1;
st[u].len=st[p].len+1;
for(;p&&!st[p].ch[c];p=st[p].fa)
st[p].ch[c]=u;
if(!p) return st[u].fa=1, void();
int q=st[p].ch[c];
if(st[q].len==st[p].len+1)
return st[u].fa=q, void();
int v=++cnt;
st[v]=st[q];
st[v].len=st[p].len+1;
st[q].fa=st[u].fa=v;
for(;p&&st[p].ch[c]==q;p=st[p].fa)
st[p].ch[c]=v;
}
vector<int> e[maxn<<1];
void build_tree()
{
for(int i=2;i<=cnt;i++)
e[st[i].fa].emplace_back(i);
}
void dfs(int u)
{
for(auto v:e[u])
dfs(v), siz[u]+=siz[v];
}
bitset<maxn<<1> vis;
int query(string &s)
{
vis.reset();
int p=1, l=0, ret=0;
int n=s.size();
for(int i=1;i<=2;i++) for(auto c:s)
{
while(p&&!st[p].ch[c-'a']) l=st[p=st[p].fa].len;
if(st[p].ch[c-'a']) p=st[p].ch[c-'a'], l++;
while(l>n) l--, p=(l==st[st[p].fa].len)?st[p].fa:p;
if(l==n&&!vis[p]) ret+=siz[p], vis[p]=1;
}
return ret;
}
void insert(string &s)
{
for(auto c:s) insert(c-'a');
}
}
string s;
int main()
{
cin>>s;
SAM::insert(s);
SAM::build_tree();
SAM::dfs(1);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>s, cout<<SAM::query(s)<<'\n';
}#include<bits/stdc++.h>
using namespace std;
#define maxn 1000006
namespace SAM
{
struct node
{
int fa, len, ch[26];
node() {memset(this, 0, sizeof *this);}
}st[maxn<<1];
int siz[maxn<<1];
int la=1, cnt=1;
void insert(int c)
{
int p=la, u=la=++cnt;
siz[u]=1;
st[u].len=st[p].len+1;
for(;p&&!st[p].ch[c];p=st[p].fa)
st[p].ch[c]=u;
if(!p) return st[u].fa=1, void();
int q=st[p].ch[c];
if(st[q].len==st[p].len+1)
return st[u].fa=q, void();
int v=++cnt;
st[v]=st[q];
st[v].len=st[p].len+1;
st[q].fa=st[u].fa=v;
for(;p&&st[p].ch[c]==q;p=st[p].fa)
st[p].ch[c]=v;
}
vector<int> e[maxn<<1];
void build_tree()
{
for(int i=2;i<=cnt;i++)
e[st[i].fa].emplace_back(i);
}
void dfs(int u)
{
for(auto v:e[u])
dfs(v), siz[u]+=siz[v];
}
bitset<maxn<<1> vis;
int query(string &s)
{
vis.reset();
int p=1, l=0, ret=0;
int n=s.size();
for(int i=1;i<=2;i++) for(auto c:s)
{
while(p&&!st[p].ch[c-'a']) l=st[p=st[p].fa].len;
if(st[p].ch[c-'a']) p=st[p].ch[c-'a'], l++;
while(l>n) l--, p=(l==st[st[p].fa].len)?st[p].fa:p;
if(l==n&&!vis[p]) ret+=siz[p], vis[p]=1;
}
return ret;
}
void insert(string &s)
{
for(auto c:s) insert(c-'a');
}
}
string s;
int main()
{
cin>>s;
SAM::insert(s);
SAM::build_tree();
SAM::dfs(1);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>s, cout<<SAM::query(s)<<'\n';
}
标签:insert,Cyclical,string,SAM,int,题解,st,vis,CF235C
From: https://www.cnblogs.com/redacted-area/p/18379568