投稿
  1. 高性能架构探索首页
  2. C/C++

HihoCoder 后缀自动机入门1-6题解

admin • • C/C++ • 阅读 123

比起后缀数组，我觉得后缀自动机比较好理解也。。。

#1441 : 后缀自动机一·基本概念

endpos集合相同的子串才是一个同一个状态。暴力模拟即可。

HihoCoder 后缀自动机入门1-6题解

#include<bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;
typedef long long ll;
tr1::unordered_map<string,ll> mmp;
tr1::unordered_map<ll,string> shortest,longest; 
int main(){
    string s,ss;
    cin>>s;
    int n,lens=s.size();
    ll state;
    for(int i=0;i<lens;i++)
        for(int j=1;j<=lens-i;j++){
            state=0;
            ss=s.substr(i,j);
            for(int k=0;k<=lens-j;k++){
                if(ss==s.substr(k,j)) state|=(1ll<<(k+j-1));
            }
            if(!shortest.count(state)||shortest[state].size()>j) shortest[state]=ss;
            if(!longest.count(state)||longest[state].size()<j) longest[state]=ss;
            mmp[ss]=state;
        }
    cin>>n;
    while(n--){
        cin>>ss;
        state=mmp[ss];
        cout<<shortest[state]<<" "<<longest[state];
        for(int i=0;i<lens;i++){
            if(state&(1ll<<i)) printf(" %d",i+1);
        }
        printf("n");
    }
    return 0;
}

String模拟

#1445 : 后缀自动机二·重复旋律5

求不同子串的个数，而每个状态中len[i]为这个状态的最长子串长度，而它最短子串长度为len[link[i]]+1（因为它的后缀是在link[i]处断的嘛）

所以每个状态最长子串长度减去最短子串长度+1就是这个状态有多少种不同子串，然后全部加起来即可。

HihoCoder 后缀自动机入门1-6题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+11;
char s[N];
int size,last,maxlen[N];//minlen[N];
//拥有相同endpos集合的为同一状态
//对于同一状态中的字符串，他们都是该状态最长子串的后缀 
//size总状态数，last上一个状态编号，maxlen[i]：i状态包含的最长子串长度 
int link[N],trans[N][31];
//trans[i][j] 转移函数，为i状态遇到j字符会转移到哪个状态
//link[i] SuffixLinks,i状态的连续后缀在哪个状态断开 
void initsam(int n){
    size=last=1;
    for(int i=0;i<=n;i++){
        link[i]=maxlen[i]=0;//minlen[i]=0;
        for(int j=0;j<26;j++) trans[i][j]=0;
    }
}
void extend(int x){
    int cur=++size,u;
    maxlen[cur]=maxlen[last]+1;
    //Suffixpath(cur-S)路径上没有对x的转移的状态,添加到cur的转移 
    for(u=last;u&&!trans[u][x];u=link[u]) trans[u][x]=cur;
    //若Suffixpath(cur-S)路径上的状态都没有对x的转移，那么此时curlink到初状态即可 
    if(!u) link[cur]=1;
    else{
        //若Suffixpath(cur-S)路径存在有对x转移的状态u
        //而v是u遇到x后转移到的状态 
        int v=trans[u][x];
        //若v中最长的子串添加上x便是u的最长子串，此时将curlink到v 
        //也就是v状态中的子串都是cur状态中的后缀，且cur的后缀序列刚好在v处断开 
        if(maxlen[v]==maxlen[u]+1) link[cur]=v;
        else{
            //否则创建个中间状态进行转移 
            //也就是cur状态和v状态都有着部分相同的后缀，而之前这些后缀保存在v状态 
            //而v状态中还有些状态不是cur状态的后缀的，所以需要个新状态表示他们共有的后缀 
            int clone=++size;
            maxlen[clone]=maxlen[u]+1;
            memcpy(trans[clone],trans[v],sizeof(trans[v]));
            link[clone]=link[v];
        //    minlen[clone]=maxlen[link[clone]]+1;
            //原先添加x后转移到v的状态，现在都转移到中间状态 
            for(;u&&trans[u][x]==v;u=link[u]) trans[u][x]=clone;
            //最后，因为cur状态和v状态的后缀都在中间状态这里断开
            //所以cur和v都link到中间状态 
            link[cur]=link[v]=clone;
        //    minlen[v]=maxlen[link[v]]+1;
        }
    }
//    minlen[cur]=maxlen[link[cur]]+1;
    last=cur;
    return ;
}
int main(){
    scanf("%s",s);
    int lens=strlen(s);
    initsam(2*lens);
    for(int i=0;i<lens;i++) extend(s[i]-'a');
    ll ans=0;
    for(int i=2;i<=size;i++) ans+=maxlen[i]-maxlen[link[i]];
    printf("%lldn",ans);
    return 0;
}

入门往往那么容易

#1449 : 后缀自动机三·重复旋律6

要求每个长度的出现个数，endpos集合就是每个状态里子串出现的个数，那么么endpos怎么求呢，直接搬运HihoCoder的讲解了，感觉讲得很好，侵删。。。。。。

小Ho：我们明白了。一个状态st对应的|endpos(st)|至少是它儿子的endpos大小之和。这一点还是比较容易证明的。假设x和y是st的两个儿子，那么根据Suffix Link的定义，我们知道st中的子串都是x中子串的后缀，也是y中子串的后缀。所以endpos(st) ⊇ endpos(x) 并且 endpos(st) ⊇ endpos(y)。又根据Suffix Link的定义我们知道x中的子串肯定不是y中子串的后缀，反之亦然，所以endpos(x) ∩ endpos(y) = ∅。所以|endpos(st)| >= |endpos(x)| + |endpos(y)|。

小Hi：那么|endpos(st)|可能比st儿子的endpos大小之和大多少呢？

小Ho：最多就大1。并且大1的情况当且仅当st是上文提到的绿色状态，即st包含S的某个前缀时才发生。我们分析endpos(1)={1, 2, 5}就会发现，它比endpos(2) ∪ endpos(6) = {2, 5}多出来的结束位置1的原因就是状态1还包含S的长度为1的前缀"a"。更一般的情形是如果某个状态st包含S的一个前缀S[1..l]，那么一定有l∈endpos(st)，并且l不能从st的儿子中继承过来。这时就需要+1。

小Hi：没错。那么我们如何判断哪些状态应该标记成绿色状态呢？

小Ho：可以在构造SAM的时候顺手做了。回顾我们构造SAM的算法，当新加入一个字符的时候，我们至少会新建一个状态z（还可能新建一个状态y），这个状态z一定是绿色状态（y一定不是）。

小Hi：没错，我们回顾一下。先构造SAM，顺手把绿色状态标记出来。然后再对Suffix Link连成的树"自底向上"求出每一个状态的|endpos(st)|，这一步"自底向上"可以通过拓扑排序完成，我们很早之前就讲过，不再赘述。

所以就是每个添加字符的那个状态endpos大小是1，然后再对SuffixLink树进行拓扑排序，就可以得到每个状态的endpos大小了。（dfs回溯也可以）

知道每个状态endpos之后，我们又知道每个状态的最长子串长度，它的影响范围就是小于等于它的长度，所以记录下相应长度的endpos再从后往前求最大值即可。

HihoCoder 后缀自动机入门1-6题解

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+11;
struct Side{
    int v,ne;
}S[N];
char s[N];
int sn,head[N];
int size,last,len[N],link[N],trans[N][31];
int endpos[N],ans[N];
void initS(int n){
    sn=0;
    for(int i=0;i<=n;i++) head[i]=-1;
}
void addS(int u,int v){
    S[sn].v=v;
    S[sn].ne=head[u];
    head[u]=sn++;
} 
void initsam(int n){
    size=last=1;
    for(int i=0;i<n;i++){
        len[i]=link[i]=endpos[i]=0;
        for(int j=0;j<26;j++) trans[i][j]=0;
    }
}
void extend(int x){
    int cur=++size,u;
    endpos[cur]=1;
    len[cur]=len[last]+1;
    for(u=last;u&&!trans[u][x];u=link[u]) trans[u][x]=cur;
    if(!u) link[cur]=1;
    else{
        int v=trans[u][x];
        if(len[v]==len[u]+1) link[cur]=v;
        else{
            int clone=++size;
            len[clone]=len[u]+1;
            link[clone]=link[v];
            memcpy(trans[clone],trans[v],sizeof(trans[v]));
            for(;u&&trans[u][x]==v;u=link[u]) trans[u][x]=clone;
            link[cur]=link[v]=clone;
        }
    }
    last=cur;
}
void dfs(int u){
    for(int i=head[u];~i;i=S[i].ne){
        int v=S[i].v;
        dfs(v);
        endpos[u]+=endpos[v]; 
    }
}
void solve(int lens){
    initS(size);
    for(int i=1;i<=size;i++) addS(link[i],i);
    dfs(1);
    for(int i=2;i<=size;i++) ans[len[i]]=max(ans[len[i]],endpos[i]);
    for(int i=lens-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]); 
}
int main(){
    scanf("%s",s);
    int lens=strlen(s);
    initsam(2*lens);
    for(int i=0;i<lens;i++) extend(s[i]-'a');
    solve(lens);
    for(int i=1;i<=lens;i++) printf("%dn",ans[i]);
    return 0;
}

进门了却出不去

#1457 : 后缀自动机四·重复旋律7

 先不管两个串，就单有一个串的时候，我们怎么算它的不同子串权值和呢，这就涉及动态规划了。

比如我们知道子串12的权值为12，那么怎么得到子串123的权值呢，很简单，12*10+3嘛。而有些状态不一定只包含一个子串，但它们加上一个新字符x后的转移状态是相同的。

也就是说，如果我们知道了某个状态的所有子串权值和sum(u),而trans[u][x]=v（u中的所有子串加上x后就变成v中的部分子串），那么sum（v）+=sum(u)*10+x*u中所有子串的个数。

知道这个转移过程之后，我们就可以根据trans确定拓扑顺序，然后在上面进行转移。

那如果是两个串，我们也可以像前面后缀数组一样，用一个不会出现的字符间隔开，然后把它们连接起来。这里使用：,因为：的ascii码值为9的ascii值+1，好处理。

然后有些状态中就会含有一些含：的子串，而这些子串是不合法的，所以我们转移的时候跳过这些不合法的子串即可，怎么跳过呢，就是不对trans[u][:]进行处理。

那么新的转移过程就是sum（v）+=sum(u)*10+x*u中所有合法子串的个数。

HihoCoder 后缀自动机入门1-6题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+11,md=1e9+7;
char s[N];
ll sum[N];
queue<int> q;
int du[N],fcnt[N];
int size,last,len[N],link[N],trans[N][21];
void initsam(int n){
    size=last=1;
    for(int i=0;i<=n;i++){
        len[i]=link[i]=0;
        for(int j=0;j<11;j++) trans[i][j]=0;
    }
}
void extend(int x){
    int cur=++size,u;
    len[cur]=len[last]+1;
    for(u=last;u&&!trans[u][x];u=link[u]) trans[u][x]=cur;
    if(!u) link[cur]=1;
    else{
        int v=trans[u][x];
        if(len[v]==len[u]+1) link[cur]=v;
        else{
            int clone=++size;
            len[clone]=len[u]+1;
            link[clone]=link[v];
            memcpy(trans[clone],trans[v],sizeof(trans[v]));
            for(;u&&trans[u][x]==v;u=link[u]) trans[u][x]=clone;
            link[cur]=link[v]=clone;
        }
    }
    last=cur;
    return ;
}
void solve(){
    for(int i=1;i<=size;i++){
        sum[i]=fcnt[i]=0;
        for(int j=0;j<11;j++){
            if(trans[i][j]) du[trans[i][j]]++;
        }
    }
    fcnt[1]=1;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<11;i++){
            int v=trans[u][i];
            if(!v) continue;
            if(i!=10){
                fcnt[v]+=fcnt[u];
                sum[v]=(sum[v]+(sum[u]*10%md+i*fcnt[u])%md)%md;
            }//不转移含：的子串 
            du[v]--;
            if(!du[v]) q.push(v);
        }
    }
}
int main(){
    int n;
    initsam(N-1);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",s);
        int lens=strlen(s);
        for(int j=0;j<lens;j++) extend(s[j]-'0');
        if(i!=n-1) extend(10);//类似后缀数组中用#分隔两个串 
    }
    solve();
    ll ans=0;
    for(int i=1;i<=size;i++) ans=(ans+sum[i])%md;
    printf("%lldn",ans);
    return 0;
}

如果要说个建议

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

如果串不循环旋转的话，那就是T串在S串中出现的次数，也就是看T串在S串的SAM中是哪个状态u，那么endpos[u]就是答案了。

而找T串在S串的SAM中的状态的过程，其实也类似于找T串和S串的LCS(最长公共子串),如果到达某个状态的LCS是T串的长度，这时就找到了。

怎么用SAM找S串和T串的LCS呢，我们对S串建SAM,那么接下来用T串在S串上面匹配。一开始u等于初始状态，而lcs=0。

对于T[i],如果trans[u][T[i]]不为空的话，很明显lcs++，然后u=trans[u][T[i]]。而当trans[u][T[i]]为空怎么办 ，我们就可以根据link[u]，suffix-path(u->S)向前找trans[u][T[i]]不为空的状态。

而这个过程就类似于KMP中失配时，按next数组往回找的过程。若一直到最初状态，rans[u][T[i]]依旧为空，那么说明S串中无T[i]字符，让u为最初状态，lcs为0。

while(u!=1&&!trans[u][x]) u=link[u],lcs=len[u];//往回找trans[u][x]不为空的状态
if(trans[u][x]) lcs++,u=trans[u][x];
else u=1,lcs=0;

而这个的T串还会进行循环，对于循环串的一种解决办法就是把它拆成一条链，把原来的串拷贝一份放到后面。T[i]'=T'[n+i]=T[i]

然后遍历T'[i],求出在每个位置T'[i]结束的最长公共子串，可以知道u和lcs。如果这时lcs>=T串的长度n，那我们就得到了一个公共子串T'[i-lcs+1 .. i]。

这个子串在S中出现的次数是|endpos(u)|，又恰好包含T的循环同构串T'[i-n+1 .. i]。而像aaa串，它某些循环串是相同的，这时就每个状态u只统计一次即可。

但还有一种情况,要区分T'[i-lcs+1 .. i]出现次数和T'[i-n+1 .. i]的出现次数。lcs>=n，T'[i-n+1 .. i]是T'[i-lcs+1 .. i]不一定在同一个状态u。

T'[i-n+1 .. i]是T'[i-lcs+1 .. i]长度为n的后缀，可能在suffix-path(u->S)上，出现次数比T'[i-lcs+1 .. i]多（HihoCoder中这里应该是打错了）。

这时也好处理，我们顺着suffix-path(u->S)往回找，找到最靠近S且最长子串长度仍然大于等于n的即可。

HihoCoder 后缀自动机入门1-6题解

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+11;
struct Side{
    int v,ne;
}S[N];
char s[N],ss[N];
int sn,head[N];
int size,last,len[N],link[N],trans[N][31];
int endpos[N],vis[N],tu[N];
void initS(int n){
    sn=0;
    for(int i=0;i<=n;i++) head[i]=-1;
}
void addS(int u,int v){
    S[sn].v=v;
    S[sn].ne=head[u];
    head[u]=sn++;
}
void initsam(int n){
    size=last=1;
    for(int i=0;i<n;i++){
        len[i]=link[i]=endpos[i]=0;
        for(int j=0;j<26;j++) trans[i][j]=0;
    }
}
void extend(int x){
    int cur=++size,u;
    endpos[cur]=1;
    len[cur]=len[last]+1;
    for(u=last;u&&!trans[u][x];u=link[u]) trans[u][x]=cur;
    if(!u) link[cur]=1;
    else{
        int v=trans[u][x];
        if(len[v]==len[u]+1) link[cur]=v;
        else{
            int clone=++size;
            len[clone]=len[u]+1;
            link[clone]=link[v];
            memcpy(trans[clone],trans[v],sizeof(trans[v]));
            for(;u&&trans[u][x]==v;u=link[u]) trans[u][x]=clone;
            link[cur]=link[v]=clone;
        }
    }
    last=cur;
}
void dfs(int u){
    for(int i=head[u];~i;i=S[i].ne){
        int v=S[i].v;
        dfs(v);
        endpos[u]+=endpos[v]; 
    }
}
void tp(){
    initS(size);
    for(int i=1;i<=size;i++) addS(link[i],i);
    dfs(1);
}
int main(){
    scanf("%s",s);
    int n,lens=strlen(s);
    initsam(2*lens);
    for(int i=0;i<lens;i++) extend(s[i]-'a');
    tp();
    scanf("%d",&n);
    while(n--){
        scanf("%s",ss);
        int lenss=strlen(ss),u=1,lcs=0,ans=0,cnt=0;
        for(int i=0;i<lenss-1;i++) ss[lenss+i]=ss[i];
        for(int i=0;i<2*lenss-1;i++){
            int x=ss[i]-'a';
            while(u!=1&&!trans[u][x]) u=link[u],lcs=len[u];
            if(trans[u][x]) lcs++,u=trans[u][x];
            else u=1,lcs=0;
            //处理T[i-lcs+1]跟T[i-n+1]不同状态的情况 
            if(lcs>lenss){
                while(len[link[u]]>=lenss) u=link[u];
                lcs=len[u];
            }
            //每个状态只统计一次 
            if(lcs>=lenss&&!vis[u]){
                vis[u]=1;
                tu[cnt++]=u;
                ans+=endpos[u];
            }
        }
        for(int i=0;i<cnt;i++) vis[tu[i]]=0;
        printf("%dn",ans);
    }
    return 0;
}

那就是不要进去

#1466 : 后缀自动机六·重复旋律9

不知道怎么解释，看代码吧，等语言表达能力提升，再来更新。

HihoCoder 后缀自动机入门1-6题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+11;
struct Sam{
    int size,last,len[N],link[N],trans[N][31],sg[N];
    ll cnt[N][31];
    //cnt[i][j]为以该状态为前缀，sg函数为j的子串个数 
    Sam(){
        size=last=1;
        sg[1]=-1;
    }
    void extend(int x){
        int cur=++size,u;
        sg[cur]=-1;
        len[cur]=len[last]+1;
        for(u=last;u&&!trans[u][x]; u=link[u]) trans[u][x]=cur;
        if(!u) link[cur]=1;
        else{
            int v=trans[u][x];
            if(len[v]==len[u]+1) link[cur]=v;
            else{
                int clone=++size;
                sg[clone]=-1;
                len[clone]=len[u]+1;
                link[clone]=link[v];
                memcpy(trans[clone],trans[v],sizeof(trans[v]));
                for(;u&&trans[u][x]==v;u=link[u]) trans[u][x]=clone;
                link[cur]=link[v]=clone;
            }
        }
        last=cur;
    }
    int Sg(int u){
        if(sg[u]!=-1) return sg[u];
        int vis[31];
        for(int i=0;i<30;i++) vis[i]=0;
        for(int i=0;i<26;i++){
            int v=trans[u][i];
            if(v){
                vis[Sg(v)]=1;
                for(int j=0;j<30;j++) cnt[u][j]+=cnt[v][j];
            }
        }
        for(int i=0;i<30;i++){
            if(!vis[i]){
                sg[u]=i;
                cnt[u][i]++;
                break;
            }
        }
        for(int i=0;i<30;i++) cnt[u][30]+=cnt[u][i];
        return sg[u];
    }
}A,B;
ll k;
char a[N],b[N],ansa[N],ansb[N]; 
int solvea(int u,int p){
    //因为先找A串，B串此时为空串，这里就是看 
    //B串sg不为A当前构造的这个串的sg的串有多少个
    ll sum=B.cnt[1][30]-B.cnt[1][A.sg[u]];
    //如果sum大于等于k，说明接下来再去构造B串即可
    //此时A串就是字典序最小的
    if(sum>=k){
        ansa[p]='';
        return u;    
    }
    k-=sum;
    for(int i=0;i<26;i++){
        int v=A.trans[u][i];
        if(v){
            sum=0;
            //这里就是算当A串的p位为'a'+i时，B串可能的串有多少种 
            for(int j=0;j<30;j++){
                sum+=A.cnt[v][j]*(B.cnt[1][30]-B.cnt[1][j]);
            }
            //如果sum小于k，说明A串的p位为'a'+i的话，不能达到k 
            //还得往下一个字符找 
            if(sum<k) k-=sum;
            else{
                //否则，A串的p位为'a'+i，继续去找p+1为 
                ansa[p]='a'+i;
                return solvea(v,p+1); 
            }
        }
    }
    return 0;
}
void solveb(int u,int p,int x){
    k-=(B.sg[u]!=x); 
    if(!k){
        ansb[p]='';
        return ;
    }
    for(int i=0;i<26;i++){
        int v=B.trans[u][i];
        //这里就是看，B串的p位为'a'+i接下来能有多少能可能的串
        ll sum=B.cnt[v][30]-B.cnt[v][x];
        //同A串 
        if(sum<k) k-=sum;
        else{
            ansb[p]='a'+i;
            solveb(v,p+1,x);
            return ;
        }
    }
}
int main(){
    scanf("%lld%s%s",&k,a,b);
    int lena=strlen(a),lenb=strlen(b);
    for(int i=0;i<lena;i++) A.extend(a[i]-'a');
    for(int i=0;i<lenb;i++) B.extend(b[i]-'a');
    //预处理出两个字符串的每个状态的sg和cnt 
    A.Sg(1);B.Sg(1); 
    int u=solvea(1,0);
    if(!u) printf("NOn");
    else{
        solveb(1,0,A.sg[u]);
        printf("%sn%sn",ansa,ansb);
    }
    return 0;
}

两行泪

 

原文链接: https://www.cnblogs.com/LMCC1108/p/13338495.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    HihoCoder 后缀自动机入门1-6题解

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368517

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午6:28
下一篇 2023年3月2日 下午6:28

相关推荐