hihoCoder #1465 : 后缀自动机五·重复旋律8

时间:2024-01-04 22:07:08

http://hihocoder.com/problemset/problem/1465

求S的循环同构串在T中的出现次数

将串S变成SS

枚举SS的每个位置i,求出以i结尾的SS的子串 与 T的最长公共子串

若长度>=|S|,说明以i结尾的S的循环同构串在T中出现过

假设最后匹配i到达了后缀自动机的a节点

沿着a的parent树以直向上走,走到离根最近的 匹配长度>=|S|的节点b

b的在parent树中的子树 叶子节点个数 即为这个以i结尾的循环同构串在T中的出现次数

#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 1000001 char s[N<<]; int ch[N<<][],tot=;
int last=,p,q,np,nq;
int fa[N<<],len[N<<];
int r[N<<]; int v[N<<];
int sa[N<<]; int use[N<<]; int now,now_len;
long long ans; void extend(int c)
{
len[np=++tot]=len[last]+;
for(p=last;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=;
else
{
q=ch[p][c];
if(len[q]==len[p]+) fa[np]=q;
else
{
nq=++tot;
fa[nq]=fa[q];
memcpy(ch[nq],ch[q],sizeof(ch[nq]));
fa[q]=fa[np]=nq;
len[nq]=len[p]+;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
last=np;
} void build()
{
scanf("%s",s+);
int n=strlen(s+);
for(int i=;i<=n;++i)
{
r[tot+]=;
extend(s[i]-'a');
}
for(int i=;i<=tot;++i) v[len[i]]++;
for(int i=;i<=n;++i) v[i]+=v[i-];
for(int i=;i<=tot;++i) sa[v[len[i]]--]=i;
for(int i=tot;i;--i) r[fa[sa[i]]]+=r[sa[i]];
} void find(int c,int n,int tim)
{
while(now && !ch[now][c]) now=fa[now],now_len=len[now];
if(!now)
{
now=;
now_len=;
}
else now=ch[now][c],now_len++;
if(now_len>n)
while(len[fa[now]]>=n)
{
now=fa[now];
now_len=len[now];
}
if(now_len>=n && use[now]!=tim)
{
use[now]=tim;
ans+=r[now];
}
// printf("%d\n",ans);
} void solve()
{
int n,m,L;
scanf("%d",&n);
for(int t=;t<=n;++t)
{
scanf("%s",s+);
m=strlen(s+);
for(int i=;i<m;++i) s[m+i]=s[i];
L=*m-;
now=; now_len=;
ans=;
for(int i=;i<=L;++i) find(s[i]-'a',m,t);
cout<<ans<<'\n';
}
} int main()
{
freopen("rotate.in","r",stdin);
freopen("rotate.out","w",stdout);
build();
solve();
}
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

小Hi发现旋律可以循环,每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”,还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。

小Hi对此产生了浓厚的兴趣,他有若干段旋律,和一部音乐作品。对于每一段旋律,他想知道有多少在音乐作品中的子串(重复便多次计)和该旋律是“循环相似旋律”。

解题方法提示

输入

第一行,一个由小写字母构成的字符串S,表示一部音乐作品。字符串S长度不超过100000。

第二行,一个整数N,表示有N段旋律。接下来N行,每行包含一个由小写字母构成的字符串str,表示一段旋律。所有旋律的长度和不超过 100000。

输出

输出共N行,每行一个整数,表示答案。

样例输入
abac
3
a
ab
ca
样例输出
2
2
1