别人的后缀自动机-白红宇

别人的后缀自动机

阅读量：5291 次

发布时间：2019-06-14

本文共 9672 字，大约阅读时间需要 32 分钟。

#include
     
      #define fi first#define se second#define INF 0x3f3f3f3f#define LNF 0x3f3f3f3f3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))const double pi=4.0*atan(1.0);const double e=exp(1.0);const int maxn=4e5+8;typedef long long LL;typedef unsigned long long ULL;const LL mod=1e9+7;const ULL base=1e7+7;const int maxp=26+5;using namespace std;struct Suffix_Node{    int ch[maxp],par,len;    void init(){        NEW(ch,0);        par=len=0;    }};LL f[maxn];//用来求子串个数开的数组class Suffix_Automation{private:    Suffix_Node s[maxn];    int cur,las,siz,crp;public:    Suffix_Automation():las(1),cur(1),siz(1),crp(1){}    const void init(){        for(int i=0;i<=siz;i++) s[i].init();        las=cur=siz=crp=1;    }    const int match(const char c)const{        return s[crp].ch[c-'a'];    }    const void withdraw(const int len){
   //撤掉开头几个字母，使已匹配的剩下长度为len        while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par;        if(crp==0) crp=1;    }    const void Transfer(const int len,const char c){
   //匹配字符加上c保持长度为len        crp=s[crp].ch[c-'a'];        if(crp==0) crp=1;        withdraw(len);    }    const void ex_tend(const char c){
   //扩展新字符        int x=c-'a';        cur=++siz;        s[cur].len =s[las].len+1;        while(las!=0&&!s[las].ch[x])            s[las].ch[x]=cur,las=s[las].par;        if(las==0) s[cur].par=1;        else{            int q,nq;            q=s[las].ch[x];            if(s[q].len==s[las].len+1)                s[cur].par=q;            else{                nq=++siz;                s[nq]=s[q],s[nq].len=s[las].len+1;                s[cur].par=s[q].par=nq;                while(las!=0&&s[las].ch[x]==q)                    s[las].ch[x]=nq,las=s[las].par;            }        }        las=cur;    }    const int LCS(string t){
   //求最长公共子串        int le=0,ans=0;        for(int i=0;t[i];i++){            if(match(t[i])){                le++;                Transfer(le,t[i]);            }            else{                while(crp&&!s[crp].ch[t[i]-'a']) crp=s[crp].par;                if(crp==0) le=0,crp=1;                else le=s[crp].len+1,crp=s[crp].ch[t[i]-'a'];            }            ans=max(ans,le);        }        return ans;    }    LL getsub(){
    //求子串个数        return dfs(1)-1;    }    LL dfs(int u){        f[u]=1;        for(int i=0;i<26;++i)            if(s[u].ch[i]){                if(!f[s[u].ch[i]])                    f[u]+=dfs(s[u].ch[i]);                else f[u]+=f[s[u].ch[i]];            }        return f[u];    }}SAM;

求字典序第ｋ小子串

https://www.luogu.org/problem/P3975

#include
     
      #define fi first#define se second#define INF 0x3f3f3f3f#define LNF 0x3f3f3f3f3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))#define rep(i, a, b) for(int i=(a); i<(b); i++)#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)#define mem(a,x) memset(a,x,sizeof(a))const double pi=4.0*atan(1.0);const double e=exp(1.0);const int maxn=1e6+8;typedef long long LL;typedef long long ll;typedef unsigned long long ULL;const LL mod=1e9+7;const ULL base=1e7+7;const int maxp=26+5;using namespace std;int c[maxn],a[maxn],sum[maxn],si[maxn];struct Suffix_Node{    int ch[maxp],par,len;    void init(){        NEW(ch,0);        par=len=0;    }};class Suffix_Automation{private:    Suffix_Node s[maxn];    int cur,las,siz,crp;public:    Suffix_Automation():las(1),cur(1),siz(1),crp(1){}    const void init(){        for(int i=0;i<=siz;i++) s[i].init();        las=cur=siz=crp=1;    }    const int match(const char c)const{        return s[crp].ch[c-'a'];    }    const void withdraw(const int len){
   //撤掉开头几个字母，使已匹配的剩下长度为len        while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par;        if(crp==0) crp=1;    }    const void Transfer(const int len,const char c){
   //匹配字符加上c保持长度为len        crp=s[crp].ch[c-'a'];        if(crp==0) crp=1;        withdraw(len);    }    const void ex_tend(const char c){
   //扩展新字符        int x=c-'a';        cur=++siz;        s[cur].len =s[las].len+1;        si[cur]=1;        while(las!=0&&!s[las].ch[x])            s[las].ch[x]=cur,las=s[las].par;        if(las==0) s[cur].par=1;        else{            int q,nq;            q=s[las].ch[x];            if(s[q].len==s[las].len+1)                s[cur].par=q;            else{                nq=++siz;                s[nq]=s[q];                s[nq].len=s[las].len+1;                s[cur].par=s[q].par=nq;                while(las!=0&&s[las].ch[x]==q)                    s[las].ch[x]=nq,las=s[las].par;            }        }        las=cur;    }    const void print(int t,int k){
   //打印第k小子串,t为0表示不同位置的相同子串算作一个,t为1表示不同位置的相同子串算作多个        for(int i=1;i<=siz;i++)            c[s[i].len]++;        for(int i=1;i<=siz;i++)            c[i]+=c[i-1];        for(int i=1;i<=siz;i++)            a[c[s[i].len]--]=i;        for(int i=siz;i;i--)            if(t)                si[s[a[i]].par]+=si[a[i]];            else                si[a[i]]=1;        si[1]=0;        for(int i=siz;i;i--){            sum[a[i]]=si[a[i]];            for (int j=0;j<26;j++)                if (s[a[i]].ch[j])                    sum[a[i]]+=sum[s[a[i]].ch[j]];        }        if(k>sum[1]){            puts("-1");            return;        }        int now=1;        k-=si[now];        while(k>0){            int p=0;            while(k>sum[s[now].ch[p]]){                k-=sum[s[now].ch[p]];                p++;            }            now=s[now].ch[p];            putchar('a'+p);            k-=si[now];        }        return;    }}SAM;char s[maxn];int main(){    int t,k;    scanf("%s%d%d",s,&t,&k);    SAM.init();    for(int i=0;s[i];i++){        SAM.ex_tend(s[i]);    }    SAM.print(t,k);}

求endpos集大小

https://cn.vjudge.net/problem/HihoCoder-1465

#include
     
      #define fi first#define se second#define INF 0x3f3f3f3f#define LNF 0x3f3f3f3f3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))#define rep(i, a, b) for(int i=(a); i<(b); i++)#define per(i, a, b) for(int i=(b)-1; i>=(a); i--)#define mem(a,x) memset(a,x,sizeof(a))const double pi=4.0*atan(1.0);const double e=exp(1.0);const int maxn=2e6+8;typedef long long LL;typedef long long ll;typedef unsigned long long ULL;const LL mod=1e9+7;const ULL base=1e7+7;const int maxp=26+5;using namespace std;struct Suffix_Node{    int ch[maxp],par,len;    int w;//用于表示endpos集大小    void init(){        NEW(ch,0);        par=len=0;        w=0;    }};struct node{    int to,nxt;}g[maxn];int head[maxn],cnt;bool r[maxn];void add(int x,int y){    g[cnt].to=y;    g[cnt].nxt=head[x];    head[x]=cnt++;}class Suffix_Automation{private:    Suffix_Node s[maxn];    int cur,las,siz,crp;public:    Suffix_Automation():las(1),cur(1),siz(1),crp(1){}    const void init(){        for(int i=0;i<=siz;i++) s[i].init();        las=cur=siz=crp=1;    }    const int match(const char c)const{        return s[crp].ch[c-'a'];    }    const void withdraw(const int len){
   //撤掉开头几个字母，使已匹配的剩下长度为len        while(crp!=0&&s[s[crp].par].len>=len) crp=s[crp].par;        if(crp==0) crp=1;    }    const void Transfer(const int len,const char c){
   //匹配字符加上c保持长度为len        crp=s[crp].ch[c-'a'];        if(crp==0) crp=1;        withdraw(len);    }    const void ex_tend(const char c){
   //扩展新字符        int x=c-'a';        cur=++siz;        s[cur].len=s[las].len+1;        s[cur].w=1;        while(las!=0&&!s[las].ch[x])            s[las].ch[x]=cur,las=s[las].par;        if(las==0) {s[cur].par=1;}        else{            int q,nq;            q=s[las].ch[x];            if(s[q].len==s[las].len+1)                {s[cur].par=q;}            else{                nq=++siz;                s[nq]=s[q];                s[nq].w=0;                s[nq].len=s[las].len+1;                s[cur].par=s[q].par=nq;                while(las!=0&&s[las].ch[x]==q)                    s[las].ch[x]=nq,las=s[las].par;            }        }        las=cur;    }    int gg(){        return s[crp].w;    }    void dfs(int u){        r[u]=1;        for(int i=head[u];i!=-1;i=g[i].nxt){            if(!r[g[i].to])                dfs(g[i].to);            s[u].w+=s[g[i].to].w;        }    }    void solve(){
   //求endpos集大小        for(int i=1;i<=siz;i++){            add(s[i].par,i);        }        for(int i=1;i<=siz;i++){            if(!r[i]) dfs(i);        }    }}SAM,SAM2;char s[maxn],ss[maxn];bool vis[maxn];int main(){    memset(head,-1,sizeof(head));    scanf("%s",s);    SAM.init();    for(int i=0;s[i];i++){        SAM.ex_tend(s[i]);    }    SAM.solve();    int t,l;    scanf("%d",&t);    while(t--){        SAM2.init();        SAM.withdraw(0);        scanf("%s",ss);        l=strlen(ss);        for(int i=l;i<2*l-1;i++){            ss[i]=ss[i-l];        }        int ll=0;        int ans=0;        for(int i=0;i<2*l-1;i++){            while(!SAM2.match(ss[i])){                ll--;                if(ll<0) break;                SAM2.withdraw(ll);            }            SAM2.ex_tend(ss[i]);            SAM2.Transfer(++ll,ss[i]);            if(ll>=l) vis[i]=1;        }        ll=0;        for(int i=0;i<2*l-1;i++){            while(!SAM.match(ss[i])){                ll++;                if(ll>i) break;                SAM.withdraw(i-ll);            }            SAM.Transfer(i-ll+1,ss[i]);            if(i-ll+1>=l&&!vis[i]){                SAM.withdraw(l);                ll=i+1-l;                ans+=SAM.gg();            }        }        for(int i=0;i<2*l-1;i++){            vis[i]=0;        }        printf("%d\n",ans);    }}

转载于:https://www.cnblogs.com/Profish/p/11231000.html

你可能感兴趣的文章

VIO的Bundle Adjustment推导

查看>>

activemq5.14+zookeeper3.4.9实现高可用

查看>>