[hihocoder1465]后缀自动机+循环同构

kgxw0430 2019-03-15 原文

[hihocoder1465]

描述

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

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

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

分析

如果是求完美配对的个数，那么我们可以用KMP或者Hash完美地解决这个问题。
但是本题要求的是循环同构就可以。所以这个并不是“鸽鸽们”所认为的青铜题。
先考虑只有一段旋律的时候，怎么快速求出答案。
一般来说，对于循环同构的问题，我们再来一个相同的串拼接到一起。也就是另\(t[n+1…2*n]=t[1…n-1]\)。
假如现在KMP做，我们无法快速的求出对于t串任意长度的子串出现的次数，因此，我们要使用强大的后缀自动机了。
考虑这样一个问题，设T[i]表示以i为结尾的最长公共子串长度。假如我们已经知道了T[i-1]，那么求T[i]的过程和KMP一样的。只不过是换做了在后缀自动机上，next数组变成了fa数组。
我们现在求出了T[i]，然后它能对答案做出贡献，当且仅当T[i]>=n，n是最初t串的长度。它出现的次数为多少呢？当然是我们的siz数组已经告诉我们的。
大体思路已经明了，不过还有两种情况需要判断一下：
1、可能会出现一个串的n个循环同构里面，有重复出现的。为了判重，我们需要一个f数组。计算一次之后把它赋值为1；
2、我们当前找到了以T[i]结尾的能和s串匹配的最长长度，它的长度>=n，siz数组保存的是这个最长长度的出现次数。然而我们其实只需要保证这个匹配长度>=n就可以了，那么可能适当的减小长度，出现次数会增加。所以我们需要找到那个最小长度的符合条件的串。
什么？你问我T组数据怎么办？做T次呗，反正加起来总共长度也就1e5。

#include<bits/stdc++.h>
#define ll long long
#define rint register int
using namespace std;
const int N=2e5+10;
int t,n,m,lm,tot=1,la=1,ne[N][30],len[N],siz[N],fa[N],c[N],A[N];
char s[N],ch[N];ll ans;bool v[N];
void add(int c){
    rint p=la,np=la=++tot;siz[tot]=1;len[tot]=len[p]+1;
    for(;p&&!ne[p][c];p=fa[p]) ne[p][c]=np;
    if(!p) fa[np]=1;
    else{
        rint q=ne[p][c];
        if(len[p]+1==len[q]) fa[np]=q;
        else{
            rint nq=++tot;
            memcpy(ne[nq],ne[q],sizeof(ne[q]));
            fa[nq]=fa[q];
            fa[q]=fa[np]=nq;
            len[nq]=len[p]+1;
            for(;p&&ne[p][c]==q;p=fa[p]) ne[p][c]=nq;
        }
    }
}
void work(){
    rint p=1,l=0;
    for(int i=1;i<=m;++i){
        while(p!=1&&!ne[p][ch[i]-'a']) p=fa[p],l=len[p];
        if(ne[p][ch[i]-'a']) p=ne[p][ch[i]-'a'],l++;
        else p=1,l=0;
        if(l>lm) while(len[fa[p]]>=lm) p=fa[p],l=len[p];
        if(l>=lm&&!v[p]){
            ans+=siz[p];
            v[p]=1;
        }
    }
    printf("%lld\n",ans);
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(rint i=1;i<=n;++i) add(s[i]-'a');
    for(rint i=1;i<=tot;++i) c[len[i]]++;
    for(rint i=1;i<=tot;++i) c[i]+=c[i-1];
    for(rint i=1;i<=tot;++i) A[c[len[i]]--]=i;
    for(rint i=tot;i>0;--i){
        rint p=A[i];
        siz[fa[p]]+=siz[p];
    }
    scanf("%d",&t);
    while(t--){
        scanf("%s",ch+1);
        m=strlen(ch+1);
        for(rint i=1;i<m;++i) ch[i+m]=ch[i];
        lm=m;m=2*m-1;ans=0;
        work();memset(v,0,sizeof(v));
    }
    return 0;
}