あの旋律を何度も繰り返しでも、あの日見た光景を再現できない
无论将那段旋律重复多少次，也无法重现那一日我们看到的景象
もし切ないならば、時をまきもどしてみるかい？
若是感到惆怅的话，要试着让时光倒流吗？
NONONOーー
今が最高！
以上部分请无视
hihocoder的一套后缀数组/后缀自动机模板（并不）题
敲了⑨遍后缀板子，也是带感
没有计时，不知道和隔壁某8′59′′比怎么样 2333
后缀数组一·重复旋律
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。
小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列，相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。
小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少？
输入
第一行两个整数 N和K。1≤N≤20000 1≤K≤N
接下来有 N 个整数，表示每个音的数字。1≤数字≤100
输出
一行一个整数，表示答案。
后缀数组模板题咯。
二分答案mid，扫描height数组，看大于mid的height有没有连续出现K-1次
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
int sa[mxn],rk[mxn],ht[mxn],r[mxn];
int wa[mxn],wb[mxn],wv[mxn],cnt[mxn];
inline int cmp(int *r,int a,int b,int l){
return r[a]==r[b] && r[a+l]==r[b+l];
}
void GetSA(int *sa,int n,int m){
int *x=wa,*y=wb;
int i,j;
// for(i=0;i<m;i++)cnt[i]=0;
for(i=;i<n;i++)++cnt[x[i]=r[i]];
for(i=;i<m;i++)cnt[i]+=cnt[i-];
for(i=n-;i>=;i--)sa[--cnt[x[i]]]=i;
for(int j=,p=;p<n;j<<=,m=p){
for(p=,i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=;i<n;i++)
wv[i]=x[y[i]];
for(i=;i<m;i++)cnt[i]=;
for(i=;i<n;i++)++cnt[wv[i]];
for(i=;i<m;i++)cnt[i]+=cnt[i-];
for(i=n-;i>=;i--)sa[--cnt[wv[i]]]=y[i];
swap(x,y);
p=;x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;
}
/* printf("SA:\n");
for(i=0;i<n;i++){
printf("%d ",sa[i]);
}
puts("");*/
return;
}
void GetHt(int n){
for(int i=;i<=n;i++)rk[sa[i]]=i;
int k=;
for(int i=,j;i<n;i++){
j=sa[rk[i]-];
if(k)k--;
while(r[i+k]==r[j+k])k++;
ht[rk[i]]=k;
}
return;
}
int n,K;
bool calc(int lim){
int tmp=;
for(int i=;i<n;i++){
if(ht[i]>=lim)tmp++;
else tmp=;
if(tmp>=K)return ;
}
return ;
}
int main(){
int i,j;
n=read();K=read();
for(i=;i<n;i++)r[i]=read();
GetSA(sa,n+,);
GetHt(n);
int l=,r=n,ans=;
while(l<=r){
int mid=(l+r)>>;
if(calc(mid)){
l=mid+;
ans=mid;
}
else r=mid-;
}
printf("%d\n",ans);
return ;
}
重复旋律1
后缀数组二·重复旋律2
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。
旋律可以表示为一段连续的数列，相似的旋律在原数列不可重叠，比如在1 2 3 2 3 2 1 中 2 3 2 出现了一次，2 3 出现了两次，小Hi想知道一段旋律中出现次数至少为两次的旋律最长是多少？
输入
第一行一个整数 N。1≤N≤100000
接下来有 N 个整数，表示每个音的数字。1≤数字≤1000
输出
一行一个整数，表示答案。
后缀数组
依旧是二分长度mid，然后看连续的一段大于等于mid的height中，sa[]最大和最小的相隔有没有超过mid
研究了一下，发现如果min和max要卡常的话，在括号内计算不多的情况下define的效果比inline函数好
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
int sa[mxn],rk[mxn],ht[mxn],r[mxn];
int wa[mxn],wb[mxn],cnt[mxn];
inline int cmp(int *r,int a,int b,int l){
return r[a]==r[b] && r[a+l]==r[b+l];
}
void GetSA(int *sa,int n,int m){
int i,j,p;
int *x=wa,*y=wb;
// for(i=1;i<=m;i++)cnt[i]=0;
for(i=;i<=n;i++)++cnt[x[i]=r[i]];
for(i=;i<=m;i++)cnt[i]+=cnt[i-];
for(i=n;i;i--)sa[cnt[x[i]]--]=i;
for(j=,p=;p<n;j<<=,m=p){
for(p=,i=n-j+;i<=n;i++)y[++p]=i;
for(i=;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
for(i=;i<=m;i++)cnt[i]=;
for(i=;i<=n;i++)++cnt[x[y[i]]];
for(i=;i<=m;i++)cnt[i]+=cnt[i-];
for(i=n;i;i--)sa[cnt[x[y[i]]]--]=y[i];
swap(x,y);
p=;x[sa[]]=;
for(i=;i<=n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p:++p;
}
return;
}
void GetHT(int n){
int i,j,k=;
for(i=;i<=n;i++)rk[sa[i]]=i;
for(i=;i<=n;i++){
if(rk[i]==)continue;
if(k)--k;
j=sa[rk[i]-];
while(r[i+k]==r[j+k])k++;
ht[rk[i]]=k;
}
return;
}
#define amin(a,b) ((a)<(b)?(a):(b))
#define amax(a,b) ((a)>(b)?(a):(b))
int n;
bool solve(int lim){
int mx=sa[],mn=sa[];
for(int i=;i<=n;i++){
if(ht[i]>=lim){
mx=amax(sa[i],mx);
mn=amin(sa[i],mn);
if(mx-mn>=lim)return ;
}
else mx=mn=sa[i];
}
return ;
}
int main(){
int i,j;
n=read();
for(i=;i<=n;i++)r[i]=read();
GetSA(sa,n,);
GetHT(n);
int l=,r=n,res=;
while(l<=r){
int mid=(l+r)>>;
if(solve(mid)){
res=mid;
l=mid+;
}else r=mid-;
}
printf("%d\n",res);
return ;
}
重复旋律2
后缀数组三·重复旋律3
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有共同的部分。
旋律是一段连续的数列，如果同一段旋律在作品A和作品B中同时出现过，这段旋律就是A和B共同的部分，比如在abab 在 bababab 和 cabacababc 中都出现过。小Hi想知道两部作品的共同旋律最长是多少？
输入
共两行。一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数，表示答案。
后缀数组模板题
LCP嘛
把两个串连起来，中间用特殊符号隔开
扫一遍height数组，ans=max(ans,height[i]) (sa[i]和sa[i-1]一个在前一个串里，一个在后一个串里)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
int sa[mxn],rk[mxn],ht[mxn],r[mxn];
int wa[mxn],wb[mxn],cnt[mxn];
inline int cmp(int *r,int a,int b,int l){
return r[a]==r[b] && r[a+l]==r[b+l];
}
void GetSA(int *sa,int n,int m){
int *x=wa,*y=wb;
int i,j,p;
// for(i=0;i<m;i++)cnt[i]=0;
for(i=;i<n;i++)cnt[x[i]=r[i]]++;
for(i=;i<m;i++)cnt[i]+=cnt[i-];
for(i=n-;i>=;i--)sa[--cnt[x[i]]]=i;
for(j=,p=;p<n;j<<=,m=p){
p=;for(i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=;i<m;i++)cnt[i]=;
for(i=;i<n;i++)++cnt[x[y[i]]];
for(i=;i<m;i++)cnt[i]+=cnt[i-];
for(i=n-;i>=;i--)sa[--cnt[x[y[i]]]]=y[i];
swap(x,y);
p=;x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;
}
return;
}
void GetHT(int n){
int i,j,k=;
for(i=;i<=n;i++)rk[sa[i]]=i;
for(i=;i<n;i++){
if(k)k--;
j=sa[rk[i]-];
while(r[i+k]==r[j+k])k++;
ht[rk[i]]=k;
}
return;
}
void solve(int n,int ed){
int res=;
for(int i=;i<=ed;i++){
if((sa[i]<=n && sa[i-]>n)||(sa[i]>n && sa[i-]<=n))
res=max(res,ht[i]);
}
printf("%d\n",res);
return;
}
char s[mxn];
int main(){
int i,j;
scanf("%s",s);
int len=strlen(s);
for(i=;i<len;i++)r[i]=s[i]-'a'+;
r[len]=;
int ed=len;
scanf("%s",s);
len=strlen(s);
for(i=;i<len;i++)r[ed+i]=s[i]-'a'+;
len+=ed;
GetSA(sa,len+,);
GetHT(len);
solve(ed,len);
return ;
}
重复旋律3
后缀数组四·重复旋律4
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。
输入
一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数，表示答案k。
后缀数组 ST表
这题有点带感。
枚举循环节的长度，然后枚举循环节的整数倍位置作为起点，算一下每一段之间的LCP，再花式处理一下边角情况即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
int sa[mxn],rk[mxn],ht[mxn],r[mxn];
int wa[mxn],wb[mxn],cnt[mxn];
inline int cmp(int *r,int a,int b,int l){return r[a]==r[b] && r[a+l]==r[b+l];}
void GetSA(int *sa,int n,int m){
int *x=wa,*y=wb;
int i,j,p;
// for(i=0;i<m;i++)cnt[i]=0;
for(i=;i<n;i++)cnt[x[i]=r[i]]++;
for(i=;i<m;i++)cnt[i]+=cnt[i-];
for(i=n-;i>=;i--)sa[--cnt[x[i]]]=i;
for(j=,p=;p<n;j<<=,m=p){
p=;for(i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=;i<m;i++)cnt[i]=;
for(i=;i<n;i++)++cnt[x[y[i]]];
for(i=;i<m;i++)cnt[i]+=cnt[i-];
for(i=n-;i>=;i--)sa[--cnt[x[y[i]]]]=y[i];
swap(x,y);
p=;x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;
}
return;
}
void GetHT(int n){
int i,j,k=;
for(i=;i<=n;i++)rk[sa[i]]=i;
for(i=;i<n;i++){
if(k)k--;
j=sa[rk[i]-];
while(r[i+k]==r[j+k])k++;
ht[rk[i]]=k;
}
return;
}
int st[mxn][],lg[mxn];
int n;
void ST_init(){
int i,j;lg[]=-;
for(i=;i<=n;i++){
lg[i]=lg[i>>]+;
st[i][]=ht[i];
}
for(j=;j<;j++)
for(i=;i<=n && i+(<<j)<=n;i++)
st[i][j]=min(st[i][j-],st[i+(<<(j-))][j-]);
return;
}
int ST(int x,int y){
if(x>y)swap(x,y); ++x;
// printf("%d %d ",x,y);
int tmp=lg[y-x+];
return min(st[x][tmp],st[y-(<<tmp)+][tmp]);
}
char s[mxn];
int main(){
int i,j;
scanf("%s",s);
n=strlen(s);
for(i=;i<n;i++)r[i]=s[i]-'a'+;
GetSA(sa,n+,);
GetHT(n);
ST_init();
int ans=;
for(i=;i<=n;i++){//枚举间隔长度
for(j=;j+i<n;j+=i){
int x=ST(rk[j],rk[j+i]);
ans=max(ans,x/i+);
if(j-i+x%i>){
x=ST(rk[j-i+x%i],rk[j+x%i]);
ans=max(ans,x/i+);
}
}
}
printf("%d\n",ans);
return ;
}
重复旋律4
后缀自动机二·重复旋律5
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中出现了多少不同的旋律？
输入
共一行，包含一个由小写字母构成的字符串。字符串长度不超过 1000000。
输出
一行一个整数，表示答案。
后缀自动机模板题
忘了开longlong WA了一串，尴尬
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct SAM{
int t[mxn][],fa[mxn],mx[mxn];
int w[mxn],rk[mxn];
int S,cnt,last;
void init(){S=cnt=last=;return;}
void insert(int c){
int np=++cnt,p=last;last=np;
mx[np]=mx[p]+;
for(;p && !t[p][c];p=fa[p])t[p][c]=np;
if(!p){fa[np]=S;}
else{
int q=t[p][c];
if(mx[q]==mx[p]+)fa[np]=q;
else{
int nq=++cnt;
mx[nq]=mx[p]+;
memcpy(t[nq],t[q],sizeof t[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
}
}
return;
}
void solve(int n){
for(int i=;i<=cnt;i++)w[mx[i]]++;
for(int i=;i<=n;i++)w[i]+=w[i-];
for(int i=cnt;i;i--)rk[w[mx[i]]--]=i;
long long ans=;
for(int i=cnt;i;i--){
int tmp=rk[i];
ans+=mx[tmp]-mx[fa[tmp]];
}
printf("%lld\n",ans);
return;
}
}sa;
char s[mxn];
int n,m;
int main(){
int i,j;
scanf("%s",s+);
n=strlen(s+);
sa.init();
for(i=;i<=n;i++)
sa.insert(s[i]-'a');
sa.solve(n);
return ;
}
重复旋律5
后缀自动机三·重复旋律6
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。
现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。
输入
共一行，包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。
输出
共Length(S)行，每行一个整数，表示答案。
后缀自动机 DP
倒着更新答案
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void write(int x){
if(x<)putchar('-'),x=-x;
if(x>)write(x/);
putchar(x%+'');
return;
}
int f[mxn];
struct SAM{
int t[mxn][],fa[mxn],mx[mxn],sz[mxn];
int w[mxn],rk[mxn];
int S,cnt,last;
void init(){
S=cnt=last=;return;
}
void insert(int c){
int np=++cnt,p=last;last=np;
mx[np]=mx[p]+;
for(;p && !t[p][c];p=fa[p])t[p][c]=np;
if(!p)fa[np]=S;
else{
int q=t[p][c];
if(mx[q]==mx[p]+)fa[np]=q;
else{
int nq=++cnt;mx[nq]=mx[p]+;
memcpy(t[nq],t[q],sizeof t[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
}
}
sz[np]=;
return;
}
void solve(int n){
for(int i=;i<=cnt;i++)++w[mx[i]];
for(int i=;i<=n;i++)w[i]+=w[i-];
for(int i=cnt;i;i--)rk[w[mx[i]]--]=i;
for(int i=cnt;i;i--){
int tmp=rk[i];
sz[fa[tmp]]+=sz[tmp];
f[mx[tmp]]=max(f[mx[tmp]],sz[tmp]);
}
for(int i=n-;i;i--)f[i]=max(f[i],f[i+]);
for(int i=;i<=n;i++){
write(f[i]);puts("");
}
return;
}
}sa;
char s[mxn];
int main(){
// freopen("in.txt","r",stdin);
int i,j;
scanf("%s",s+);
int n=strlen(s+);
sa.init();
for(i=;i<=n;i++)sa.insert(s[i]-'a');
sa.solve(n);
return ;
}
重复旋律6
后缀自动机四·重复旋律7
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。
神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集，顾名思义，这部作品集里有许多作品，但是所有的作品有一个共同特征：只用了十个音符，所有的音符都表示成0-9的数字。
现在小Hi想知道这部作品中所有不同的旋律的“和”（也就是把串看成数字，在十进制下的求和，允许有前导0）。答案有可能很大，我们需要对（10^9 + 7)取摸。
输入
第一行，一个整数N，表示有N部作品。
接下来N行，每行包含一个由数字0-9构成的字符串S。
所有字符串长度和不超过 1000000。
输出
共一行，一个整数，表示答案 mod （10^9 + 7)。
后缀自动机 DFS DP
这题挺带感的。
倒着把字符串建成后缀自动机，统计出每个状态结点出现的次数后，从root开始记忆化搜索（DP？）每种转移方式的贡献
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int mod=1e9+;
const int mxn=;
LL f[mxn];
struct SAM{
int t[mxn][],fa[mxn],mx[mxn];
int sz[mxn];
int S,cnt,last;
void init(){S=cnt=last=;return;}
void insert(int c){
int np=++cnt,p=last;last=np;
mx[np]=mx[p]+;
for(;p && !t[p][c];p=fa[p])t[p][c]=np;
if(!p)fa[np]=S;
else{
int q=t[p][c];
if(mx[q]==mx[p]+)fa[np]=q;
else{
int nq=++cnt;
mx[nq]=mx[p]+;
memcpy(t[nq],t[q],sizeof t[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
}
}
return;
}
void solve(int u){
if(f[u]!=-)return;
f[u]=sz[u]=;
for(int i=;i<;i++){
if(t[u][i])solve(t[u][i]);
else continue;
int v=t[u][i];
// printf("u:%d v:%d %lld %d\n",u,v,f[u],f[v]);
(f[u]+=f[v]*%mod+(LL)i*(sz[v]+))%=mod;
sz[u]+=sz[v]+;
if(sz[u]>=mod)sz[u]-=mod;
}
return;
}
}sa;
int n;
char s[mxn];
int main(){
int i,j;
scanf("%d",&n);
sa.init();
for(i=;i<=n;i++){
scanf("%s",s+);
int len=strlen(s+);
sa.last=sa.S;
for(j=len;j;j--)
sa.insert(s[j]-'');
}
memset(f,-,sizeof f);
sa.solve(sa.S);
printf("%lld\n",f[]);
return ;
}
重复旋律7
后缀自动机五·重复旋律8
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。
小Hi发现旋律可以循环，每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”，还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。
小Hi对此产生了浓厚的兴趣，他有若干段旋律，和一部音乐作品。对于每一段旋律，他想知道有多少在音乐作品中的子串（重复便多次计）和该旋律是“循环相似旋律”。
输入
第一行，一个由小写字母构成的字符串S，表示一部音乐作品。字符串S长度不超过100000。
第二行，一个整数N，表示有N段旋律。接下来N行，每行包含一个由小写字母构成的字符串str，表示一段旋律。所有旋律的长度和不超过 100000。
输出
输出共N行，每行一个整数，表示答案。
后缀自动机 脑洞题
妙啊。把str串的[1~len-1]部分复制一遍接到原串后面，比如abcde就处理成abcdeabcd，在后缀自动机上跑一遍就可以匹配所有循环同构串了。
只有匹配长度大于原str串长的状态能计入答案，统计答案的时候要用vis记录已经统计过的结点，防止重复。
有些实现细节不太理解，代码基本靠抄
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int mxn=;
char s[mxn],a[mxn];
int vis[mxn],dtime=;
struct SAM{
int t[mxn][],fa[mxn],mx[mxn];
int w[mxn],rk[mxn],sz[mxn];
int S,cnt,last;
void init(){S=cnt=last=;return;}
void insert(int c){
int np=++cnt,p=last;last=np;
mx[np]=mx[p]+;
for(;p && !t[p][c];p=fa[p])t[p][c]=np;
if(!p)fa[np]=S;
else{
int q=t[p][c];
if(mx[q]==mx[p]+)fa[np]=q;
else{
int nq=++cnt;mx[nq]=mx[p]+;
memcpy(t[nq],t[q],sizeof t[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
}
}
sz[np]=;
return;
}
void ST(int n){
int i;
for(i=;i<=cnt;i++)w[mx[i]]++;
for(i=;i<=n;i++)w[i]+=w[i-];
for(i=cnt;i;i--)rk[w[mx[i]]--]=i;//cnt错打成n WA1
for(i=cnt;i;i--){
int tmp=rk[i];
sz[fa[tmp]]+=sz[tmp];
}
return;
}
#define amin(a,b) ((a)<(b)?(a):(b))
void solve(int m){
int now=S,tmp=,res=;
int ed=m+m-;
for(int i=,c;i<=ed;i++){
tmp++;
c=a[i]-'a';
while(now> && !t[now][c])now=fa[now];
tmp=amin(tmp,mx[now]+);
if(t[now][c])now=t[now][c];
while(mx[fa[now]]>=m)now=fa[now];
tmp=amin(tmp,mx[now]);
if(tmp>=m){
if(vis[now]!=dtime){
vis[now]=dtime;
res+=sz[now];
}
}
}
printf("%d\n",res);
return;
}
}sa;
int n;
int main(){
int i,j;
scanf("%s",s+);
sa.init();
int len=strlen(s+);
for(i=;i<=len;i++)sa.insert(s[i]-'a');
sa.ST(len);
scanf("%d",&n);
while(n--){
scanf("%s",a+);
int m=strlen(a+);
for(i=;i<m;i++)a[m+i]=a[i];
++dtime;
sa.solve(m);
}
return ;
}
重复旋律8
后缀自动机六·重复旋律9
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段字符构成的字符串。
现在小Hi已经不满足于单单演奏了！他通过向一位造诣很高的前辈请教，通过几周时间学习了创作钢琴曲的基本理论，并开始对曲目做改编或者原创。两个月后，小Hi决定和前辈进行一场创作曲目的较量！
规则是这样的，有两部已知经典的作品，我们称之为A和B。经典之所以成为经典，必有其经典之处。
刚开始，纸上会有一段A的旋律和一段B的旋律。两人较量的方式是轮流操作，每次操作可以选择在纸上其中一段旋律的末尾添加一个音符，并且要求添加完后的旋律依然是所在作品的旋律（也就是A或B的一个子串）。谁词穷了（无法进行操作）就输了。
小Hi和前辈都足够聪明，但是小Hi还是太年轻，前辈打算教训他一顿。前辈表示会和小Hi进行K次较量，只要小Hi赢了哪怕一次就算小Hi获得最终胜利。但是前提是开始纸上的两段旋律需要他定。小Hi欣然同意，并且表示每次较量都让前辈先操作。
前辈老谋深算，显然是有备而来。他已经洞悉了所有先手必胜的初始(两段)旋律。第i天前辈会挑选字典序第i小的初始(两段)旋律来和小Hi较量。那么问题来了，作为吃瓜群众的你想知道，最后一天即第K天，前辈会定哪两个旋律呢？
初始时两段旋律的字典序比较方式是先比较前一个旋律字典序，一样大则比较后一旋律的字典序。
输入
第一行包含一个正整数，K。K<=10^18
第二行包含一个非空的仅有小写字母构成的字符串，表示作品A。|A|<=10^5
第三行包含一个非空的仅有小写字母构成的字符串，表示作品B。|B|<=10^5
输出
输出共两行，每行一个字符串（可能为空），表示答案。
如果无解则只输出一行"NO"。
后缀自动机 博弈论 sg函数 码农题？
可能算得上是码农题……想明白原理以后就只剩下背板了233
好像有道“讲故事”也是这个套路。
对于单个自动机，可以用sg函数的基本定义（mex）算出每个结点的sg值。
多局面sg游戏，sg异或和不为0的时候先手必胜。
为了优先确保A部分的字典序最小，先在A串的SAM上计算。设当前结点的sg值为nowsg，若加上B串的SAM上所有sg值不为nowsg的状态后总数大于K，就转到B串的自动机上计算，否则继续在A串上贪心转移使得字典序最小……
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
const int mxn=;
struct SAM{
int t[mxn][],fa[mxn],sz[mxn],mx[mxn];
int w[mxn],rk[mxn];
LL smm[mxn],ssg[mxn][];
int sg[mxn];//
int S,cnt,last;
void init(){S=cnt=last=;return;}
void insert(int c){
int np=++cnt,p=last;last=np;
mx[np]=mx[p]+;
for(;p && !t[p][c];p=fa[p])t[p][c]=np;
if(!p)fa[np]=S;
else{
int q=t[p][c];
if(mx[q]==mx[p]+)fa[np]=q;
else{
int nq=++cnt;mx[nq]=mx[p]+;
memcpy(t[nq],t[q],sizeof t[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
}
}
sz[np]=;
return;
}
void TST(int n){
int i;
for(i=;i<=cnt;i++)++w[mx[i]];
for(i=;i<=n;i++)w[i]+=w[i-];
for(i=cnt;i;i--)rk[w[mx[i]]--]=i;
for(int i=cnt,c;i;i--){
c=rk[i];
sz[fa[c]]+=sz[c];
}
return;
}
void solve(){
bool mex[];
for(int i=cnt;i;i--){
int tmp=rk[i];
memset(mex,,sizeof mex);
for(int j=;j<;j++){
if(!t[tmp][j])continue;
int v=t[tmp][j];
mex[sg[v]]=;
for(int k=;k<;k++)
ssg[tmp][k]+=ssg[v][k];
}
sg[tmp]=;
while(mex[sg[tmp]])++sg[tmp];
++ssg[tmp][sg[tmp]];//以tmp为前缀的状态的sg值之和
smm[tmp]=;
for(int j=;j<;j++)
smm[tmp]+=ssg[tmp][j];
}
return;
}
}sa,sb;
char s[mxn],c[mxn];
LL K;
void calc(){
int now=sa.S;
LL num=;
while(){//优先处理a
bool flag=;
int sgnow=sa.sg[now];
// printf("now:%d sgnow:%d num:%lld cntb:%lld\n",
// now,sgnow,num,sb.smm[1]-sb.ssg[1][sgnow]);
if(num+sb.smm[]-sb.ssg[][sgnow]>=K)break;
//如果此时添加b串可以够K个，就不再处理A
num+=sb.smm[]-sb.ssg[][sgnow];
for(int i=;i<;i++){
if(!sa.t[now][i])continue;
int v=sa.t[now][i];
LL tmp=;
for(int j=;j<;j++)
tmp+=(LL)sa.ssg[v][j]*(sb.smm[]-sb.ssg[][j]);
if(num+tmp<K)num+=tmp;
else{
now=v;
flag=;
printf("%c",'a'+i);
break;
}
}
if(flag){printf("NO\n");return;}//26个字母都凑不够数，无解
}
printf("\n");
int sgA=sa.sg[now];
now=sb.S;
while(num<K){
if(sb.sg[now]!=sgA)num++;
if(num==K)break;
for(int i=;i<;i++){
if(!sb.t[now][i])continue;
int v=sb.t[now][i];
LL tmp=sb.smm[v]-sb.ssg[v][sgA];
if(num+tmp<K)num+=tmp;
else{
now=v;
printf("%c",'a'+i);
break;
}
}
}
return;
}
int main(){
int i,j;
cin>>K;
scanf("%s",s+);
int len1=strlen(s+);
sa.init();
for(i=;i<=len1;i++)sa.insert(s[i]-'a');
sa.TST(len1);
sa.solve();
//
scanf("%s",c+);
int len2=strlen(c+);
sb.init();
for(i=;i<=len2;i++)sb.insert(c[i]-'a');
sb.TST(len2);
sb.solve();
//
// printf("1:%lld\n",sb.smm[1]);
// for(i=0;i<27;i++)printf("%lld ",sb.ssg[1][i]);
// puts("");
calc();
return ;
}
重复旋律9