精华内容
下载资源
问答
  • 今天这里主要要讲的是后缀自动机如何转后缀树和后缀数组 后缀树 这里首先需要提一下后缀树的概念 后缀树其实相当于把所有的后缀插入一颗Trie树 然而时空复杂度都是O(N^2)的 所以我们可以把这可T

    算法学习:后缀自动机转后缀树转后缀数组

    引入

    其实这是一篇水文
    想要学后缀自动机的话去查2012年noi冬令营陈立杰讲稿
    顺便说一句,讲稿上有一些错误,多翻几篇博客加深理解。
    今天这里主要要讲的是后缀自动机如何转后缀树和后缀数组

    后缀树

    这里首先需要提一下后缀树的概念
    后缀树其实相当于把所有的后缀插入一颗Trie树
    然而时空复杂度都是O(N^2)的
    所以我们可以把这可Trie树上的某些边压缩一下
    比如这样

    这是一颗字符串banans的所有后缀组成的Trie树

    这是一颗压缩后的Trie树,也就是后缀树
    (图片来源于网络)

    从后缀自动机到后缀树

    其实操作非常简单,就是把字符串倒序插入后缀自动机,形成的parent树就是后缀树
    证明的话,考虑一对parent树上的父子关系。
    AAAAxAAAAxBAAx
    考虑这样一个字符串
    考虑串AAAAx和AAx
    显然AAx是AAAAx parent树上的父亲
    我们发现,AAx是AAAAx的后缀
    我们考虑parent树上从叶子节点到根的路径。
    每个节点表示的字符串长度集合[Min(s),Max(s)]越来越小,而且我们还会发现,父亲一定是儿子的后缀。并且儿子的Right集合是父亲的真子集。也就是父亲可能作为别的儿子的后缀
    这个时候我们对比后缀树。
    仍然是考虑一条从叶子节点到根的路径,我们会发现父亲一定是儿子的前缀。并且一个父亲可能作为很多个儿子的前缀,比如上面例子中的AAx可以作为AAAx,AAAAx,BAAx的后缀。
    你瞧,这不是和后缀自动机反着来的么!
    那么我们把字符串逆序,是不是意味着所有的前缀变后缀啦?
    那么插入后缀自动机中,形成的Parent树不就是一个逆序前的后缀树吗?
    这个时候,我们考虑对应关系。
    还是原来AAx和AAAAx的例子
    我们发现,AAx和AAAAx差了一个“AA”,BAAx和AAx差了一个“B”
    这个时候“AA”不会再分叉出去接别的后缀,说明,这条边是可以压缩的。
    那么如果我们的字符串已经逆序,AA再原串上就不会再去接别的前缀。
    那么AA就可以压缩。
    也就是后缀树上的压缩边啦。
    那么AA是什么?
    我们显然可以在插入后缀自动机的时候记录AAx的位置pos,假设AAx表示的节点为u,AAAAx表示的节点为v,那么AA对应在原串中就是pos+(Max(v)-Max(u))~pos+Max(v)
    在后缀树上这就是一条边的标记。因为这条边是可压缩的,所以只要记录这条边的首字符pos+(Max(v)-Max(u))即可。

    后缀树转后缀数组

    你一定好奇我为什么没有先贴代码。
    先不着急,代码可以一起贴。
    请你先自己yy一下,如果给你可以后缀树,怎么求后缀数组。
    后缀树是一颗Trie树。
    是一颗Trie树
    Trie树!!!
    那不就从根节点开始,按字母字典序dfs搜一下后缀树就可以了吗?
    你可能会想:哦,原来这是后缀数组的另外一种求法。不过和原来的算法没差。
    真的没差?
    原来的方法是倍增法,复杂度O(nlogn)
    可是后缀自动机的复杂度是线性的,线性的,线性的!!!
    (好吧我得承认它常数跑得太满了,再数据量不大的情况下还是更慢的,比较鸡肋)
    现在真的可以贴代码了

    代码

    #include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<map>
    #include<cmath>
    using namespace std;
    const int N = 1e6 + 10; 
    int sa[N], rank[N], s[N], n;
    void readchar() {
        char ch = getchar(); int x = 0;
        while(ch < 'a' || ch > 'z') ch = getchar();
        while(ch >= 'a' && ch <= 'z') {s[++x] = ch - 'a'; ch = getchar();}
        n = x;
    } 
    struct SAM {
        int ch[N][26], pos[N], len[N], fa[N], last, sz;
        bool val[N];
        SAM() {last = ++sz;}
        void Extend(int c, int po) {
            int p = last, np = last = ++sz;
            pos[np] = po; val[np] = true; len[np] = len[p] + 1;
            for(;p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
            if(!p) fa[np] = 1;
            else {
                int q = ch[p][c];
                if(len[q] == len[p] + 1) fa[np] = q;
                else {
                    int nq = ++sz; len[nq] = len[p] + 1;
                    memcpy(ch[nq], ch[q], sizeof(ch[q]));
                    fa[nq] = fa[q]; pos[nq] = pos[q];
                    fa[q] = fa[np] = nq;
                    for(;ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
                }
            } 
        }
    }sam;
    
    struct Suffix_Tree {
        int ch[N][26], pos[N], tp;
        bool val[N];
        void Add(int u, int v, int c) {ch[u][c] = v;}
        void Build() {
            for(int i = 1;i <= sam.sz; ++i) val[i] = sam.val[i], pos[i] = sam.pos[i];
            for(int i = 2;i <= sam.sz; ++i) 
                Add(sam.fa[i], i, s[pos[i] + sam.len[sam.fa[i]]]);
        }
        void Dfs(int u) {
            if(val[u]) sa[rank[pos[u]] = ++tp] = pos[u];
            for(int i = 0 ;i < 26; ++i) 
            if(ch[u][i]) Dfs(ch[u][i]);
        }
    }suftree;
    
    int main() {
        readchar();
        for(int i = n; i >= 1; --i) sam.Extend(s[i], i);
        suftree.Build();
        suftree.Dfs(1);
        for(int i = 1;i <= n; ++i) printf("%d ", sa[i]);
        putchar('\n');
        return 0;
    }

    是的,你没有看错,就算是以博主(我我我!)这样很常(la)数(ji)的代码也只要60行
    舒服!

    展开全文
  • 后缀数组 其实就是通过把字符串的所有后缀排序来实现一些东西。 后缀排序可以用倍增+双关键字来实现。 然后排完之后可以求出height数组,然后就可以用RMQ求LCA了。 后缀自动机 各种复杂度都是线性的,非常优秀...

    这只是个人小结,没啥大意义。

    后缀数组

    其实就是通过把字符串的所有后缀排序来实现一些东西。

    后缀排序可以用倍增+双关键字来实现。

    然后排完之后可以求出height数组,然后就可以用RMQ求LCA了。

    后缀自动机

    各种复杂度都是线性的,非常优秀。

    原理:把具有相同right集合的状态缩成一个点,这个点内的所有状态互为后缀。

    每个状态有一个minlen和maxlen,表示这个状态内的最长子串和最短子串。

    构造方法:增量构造法,考虑这个字符的加入会使之前的所有后缀增加一个字符,所以可以通过调fail树来构造。

    然后就是father的问题,如果l[p]+1=l[q]那么可以直接连father,否则直接连状态会出现问题,那么我们就新建立一个节点。

    应用:

    1、求某个子串在原串中的出现次数,在后缀节点上大标记,该子串代表的节点子树的size就是出现次数。

    转载于:https://www.cnblogs.com/ZH-comld/p/10159065.html

    展开全文
  • 天天一头雾水,真是头大呢; 也祝自己生日快乐7.12,真是海亮美好...KMP的Next数组是用来最长公共前后缀,而AC自动机的fail指针是用来搞相同后缀即可; 因为KMP只对一个模式串做匹配,而AC自动机要对多个模式串...

    天天一头雾水,真是头大呢;

    也祝自己生日快乐7.12,真是和海亮美好的回忆;

    AC自动机:自动A题的机器;显然这样说是错的;

    这个东西 我只想写一下自己的理解 然后一些总结;

    首先 它是具有KMP性质的东西,但是又是有区别的;

    KMP的Next数组是用来最长公共前后缀,而AC自动机的fail指针是用来搞相同后缀即可;

    因为KMP只对一个模式串做匹配,而AC自动机要对多个模式串做匹配。

    有可能 fail指针指向的结点对应着另一个模式串,两者前缀不同。

    也就是说,AC自动机在对匹配串做逐位匹配时,同一位上可能匹配多个模式串。

    因此 fail 指针会在字典树上的结点来回穿梭,而不像KMP在线性结构上跳转。

    首先是将模式串插入trie树中,插入操作一样,注意打标记;

    我们利用部分已经求出 fail 指针的结点推导出当前结点的 fail 指针。具体我们用BFS实现:

    考虑字典树中当前的节点u,u的父节点是p,p通过字符c的边指向u。

    假设深度小于u的所有节点的 fail指针都已求得。那么p的 fail指针显然也已求得。

    我们跳转到p的 fail指针指向的结点 fail[p] ;

    如果结点 fail[p]通过字母 c 连接到的子结点 w 存在:

    则让u的fail指针指向这个结点 w ( fail[u]=w)。

    相当于在 p 和 fail[p] 后面加一个字符 c ,就构成了 fail[u] 。

    如果 fail[p]通过字母 c 连接到的子结点 w 不存在:

    那么我们继续找到 fail[fail[p]] 指针指向的结点,重复上述判断过程,一直跳 fail 指针直到根节点。

    如果真的没有,就令 fail[u]= 根节点。

    然后建出AC自动机,搞出每个的fail指针,然后拿文本串在上面跑一下就行了;

    模板一

    #include<bits/stdc++.h>
    using namespace std;
    
    template<typename T>inline void read(T &x) {
        x=0;
        register int f=1;
        register char ch=getchar();
        while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }
    
    const int N=5000010;
    int n,m,trie[N][26],fail[N],e[N],idx;
    char s[1000005];
    
    inline void insert(char *s) {
        int p=0;
        for(int i=0;s[i];i++) {
            int ch=s[i]-'a';
            if(!trie[p][ch]) trie[p][ch]=++idx;
            p=trie[p][ch];
        }
        e[p]++;
    }
    
    inline void build() {
        queue<int> q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]);
        while(q.size()) {
            int k=q.front(); q.pop();
            for(int i=0;i<26;i++) {
                if(trie[k][i]) {
                    fail[trie[k][i]]=trie[fail[k]][i];
                    q.push(trie[k][i]);
                }
                else trie[k][i]=trie[fail[k]][i];
            }
        }
    } 
    
    int query(char *t) {
        int p=0,res=0;
        for(int i=0;t[i];i++) {
            p=trie[p][t[i]-'a'];
            for(int j=p;j&&~e[j];j=fail[j])res+=e[j],e[j]=-1;
        }
        return res;
    }
    
    int main() {
        read(n);
        for(int i=1;i<=n;i++) {
            scanf("%s",s);
            insert(s);
        }
        build();
        scanf("%s",s);
        int ans=query(s);
        printf("%d\n",ans);
    } 
    View Code

    模板二:

    #include<bits/stdc++.h>
    using namespace std;
    template<typename T>inline void read(T &x) {
        x=0;
        register int f=1;
        register char ch=getchar();
        while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }
    string mob[300010];
    int e[300010],trie[300010][26],fail[300010],ans[300010],n,idx;
    
    inline void insert(string s,int v) {
        int p=0;
        for(int i=0;i<s.size();i++) {
            int ch=s[i]-'a';
            if(!trie[p][ch]) trie[p][ch]=++idx;
            p=trie[p][ch];
        }
        e[p]=v;
    }
    
    inline void build() {
        queue<int> q;
    //    memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]);
        while(q.size()) {
            int k=q.front(); q.pop();
            for(int i=0;i<26;i++) {
                if(trie[k][i]) {
                    fail[trie[k][i]]=trie[fail[k]][i];
                    q.push(trie[k][i]);
                }
                else trie[k][i]=trie[fail[k]][i];
            }
        }
    } 
    
    inline void query(string s) {
        int p=0;
        for(int i=0;i<s.size();i++){
            p=trie[p][s[i]-'a'];
            for(int j=p;j;j=fail[j])    ans[e[j]]++;
        }
    }
    
    int main() {
    //    freopen("a.in","r",stdin);
    //    freopen("a.out","w",stdout);
        while(scanf("%d",&n),n) {
            idx=0;
    //        clear();
            memset(e,0,sizeof(e));
            memset(ans,0,sizeof(ans));
            memset(trie,0,sizeof(trie));
            memset(fail,0,sizeof(fail));
            for(int i=1;i<=n;i++) {
                cin>>mob[i];
                insert(mob[i],i);
            }
            build();
            string t;
            cin>>t;
            query(t);
            int temp=0;
            for(int i=1;i<=n;i++)if(ans[i]>temp)    temp=ans[i];
            cout<<temp<<endl;
            for(int i=1;i<=n;i++)if(ans[i]==temp)    cout<<mob[i]<<"\n";
        }
        return 0;
    }
    View Code

    模板三:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=5000010;
    template<typename T>inline void read(T &x) {
        x=0;
        register int f=1;
        register char ch=getchar();
        while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }
    int n,idx,lin[200010],tot;
    int trie[200010][26],fail[200010],e[200010],size[200010];
    string s,t;
    int ans[200010];
    
    struct gg {
        int x,y,next;
    }a[N<<1];
    
    inline void insert(string s,int v) {
        int p=0;
        for(int i=0;i<s.size();i++) {
            int ch=s[i]-'a';
            if(!trie[p][ch]) trie[p][ch]=++idx;
            p=trie[p][ch];
        }
        e[v]=p;
    }
    
    inline void build() {
        queue<int> q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++) if(trie[0][i]) q.push(trie[0][i]);
        while(q.size()) {
            int k=q.front(); q.pop();
            for(int i=0;i<26;i++) {
                if(trie[k][i]) {
                    fail[trie[k][i]]=trie[fail[k]][i];
                    q.push(trie[k][i]);
                }
                else trie[k][i]=trie[fail[k]][i];
            }
        }
    } 
    
    inline void add(int x,int y) {
        a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
    }
    
    inline void dfs(int x) {
        for(int i=lin[x];i;i=a[i].next) {
            int y=a[i].y;
            dfs(y);
            size[x]+=size[y];
        }
    }
    
    int main() {
    //    freopen("a.in","r",stdin);
    //    freopen("a.out","w",stdout);
        read(n);
        for(int i=1;i<=n;i++) {
            cin>>s;
            insert(s,i);
        } 
        build();
        cin>>t;
        int p=0;
        for(int i=0;i<t.size();i++) {
            p=trie[p][t[i]-'a'];
            size[p]++;
        }
        for(int i=1;i<=idx;i++) add(fail[i],i);//建个fail树 
        dfs(0);
        for(int i=1;i<=n;i++) printf("%d\n",size[e[i]]);
        return 0;
    }
    View Code

    来几道比较有意思的题目:

    病毒:

    这个题目没有文本串,我们可以想象出一个符合条件的文本串,如果存在,那么这个文本串一定不能在病毒串组成的trie上匹配,那么他一定会沿着fail指针一直跳,

    怎么才能一直跳,有环,对啊,并且这里容易想明白的是,我们一定不能跳到一个有结束标记的节点;

    但是直接写的话,我们一定会失败,为什么,我们考虑一种情况,如果在跳fail指针的时候,我们顺着fail指针调到一个有结束节点的地方,那么我们也是不能选择这个跳,

    我们把这些情况预处理出来就可以了;dfs找环是否存在就好了;

    #include<bits/stdc++.h>
    using namespace std;
    template<typename T>inline void read(T &x)
    {
        x=0;
        register int f=1;
        register char ch=getchar();
        while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }
    
    int n,idx,flag,trie[3000010][26],e[3000010],fail[3000010],vis[3000010];
    string s;
    
    inline void insert(string s) {
        int p=0;
        for(int i=0;i<s.size();i++) {
            int ch=s[i]-'0';
            if(!trie[p][ch])  trie[p][ch]=++idx;
            p=trie[p][ch];
        }
        e[p]=1;
    }
    
    inline void build() {
        queue<int> q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<10;i++) 
            if(trie[0][i]) q.push(trie[0][i]);
        while(q.size()) {
            int k=q.front();q.pop();
            for(int i=0;i<10;i++) {
                if(trie[k][i])  {
                    fail[trie[k][i]]=trie[fail[k]][i];
                    q.push(trie[k][i]);
                }
                else trie[k][i]=trie[fail[k]][i];
            }
        }
    }
    
    inline void dfs(int x) {
        if(flag) return ;
        for(int i=0;i<=1;i++) {
            int p=trie[x][i];
            if(!vis[p]&&!e[p]) {
                vis[p]=1;
                dfs(p);
                vis[p]=0;//还原现场; 
            }
            else if(vis[p]&&!e[p]) {
                flag=1;
                return ;
            }
        }
    }
    
    int main() {
    //    freopen("a.in","r",stdin);
    //    freopen("a.out","w",stdout);
        read(n);    
        for(int i=1;i<=n;i++) {
            cin>>s;
            insert(s);
        } 
        build();
        vis[0]=1;
        for(int i=1;i<=idx;i++) {
            int k=i,m=0;
            while(k>0) {
                if(e[k])
                m=k;
                k=fail[k];
            }
            k=i;
            if(m==0) continue;
            while(k>0) {
                if(k==m) break;
                e[k]=1;
                k=fail[k];
            }
        }
        dfs(0);
        if(flag) {
            printf("TAK\n");
        }
        else {
            printf("NIE\n");
        }
        return 0;
    }
    View Code

    玄武密码;

    这个题目让我们找能匹配的最长前缀,显然我们预处理出来所有情况,在匹配的时候,当不能匹配的时候退出,此时就是最大长度;

    //#include<bits/stdc++.h>
    #include<iomanip>
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<deque>
    #include<cmath>
    #include<ctime>
    #include<cstdlib>
    #include<stack>
    #include<algorithm>
    #include<vector>
    #include<cctype>
    #include<utility>
    #include<set>
    #include<bitset>
    #include<map>
    #define INF 1000000000
    #define ll long long
    #define min(x,y) ((x)>(y)?(y):(x))
    #define max(x,y) ((x)>(y)?(x):(y))
    #define RI register ll
    #define db double
    #define EPS 1e-8
    using namespace std;
    #define mann 100005
    #define maxn 10000005
    template<typename T>inline void read(T &x) {
        x=0;
        register int f=1;
        register char ch=getchar();
        while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }
    int n,m,idx;
    int trie[maxn][4],fail[maxn],e[maxn],f[maxn];
    char s[maxn],d[4],b[mann][105];
    
    inline char change(char c)
    {
        if(c=='E') return d[0];
        else if(c=='S') return d[1];
        else if(c=='W') return d[2];
        else return d[3];
    }
    
    
    inline void insert(char *s) {
        int p=0,len=strlen(s);
        for(int i=0;i<len;i++) {
            int ch=s[i]-'a';
            if(!trie[p][ch])  trie[p][ch]=++idx;
            p=trie[p][ch];
        }
        e[p]=1;
    }
    
    inline void build() {
        queue<int> q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<4;i++) if(trie[0][i]) q.push(trie[0][i]);
        while(q.size()) {
    //    cout<<"((()))"<<endl; 
            int k=q.front(); q.pop();
            for(int i=0;i<4;i++) {
                if(trie[k][i]) {
                    fail[trie[k][i]]=trie[fail[k]][i];
                    q.push(trie[k][i]);
                }
                else trie[k][i]=trie[fail[k]][i];
            }
        }
    } 
    
    inline void query(char *s) {
        int len=strlen(s),p=0,k;
        for(int i=0;i<len;i++) {
            int ch=s[i]-'a';
            k=trie[p][ch];
            while(k>0) {
                if(f[k]) break;//不用再跳fail了,已被更新; 
                f[k]=1;
                k=fail[k];
            }
            p=trie[p][ch];
        }
    }
    
    inline int ask(char *t) {
        int len=strlen(t),p=0;
        for(int i=0;i<len;i++) {
            int ch=t[i]-'a';
            p=trie[p][ch];
            if(!f[p]) return i;
        }
        return len;
    }
    
    int main() {
    //    freopen("1.in","r",stdin);
    //    freopen("a.out","w",stdout);
        d[0]='a',d[1]='b',d[2]='c',d[3]='d';
        read(n); read(m);
        scanf("%s",s);
        for(int i=0;i<n;i++) {
            s[i]=change(s[i]);
        } 
        for(int i=1;i<=m;i++) {
            scanf("%s",b[i]);
            int len=strlen(b[i]);
            for(int j=0;j<len;j++)
                b[i][j]=change(b[i][j]);
            insert(b[i]);
        }
        build();
        query(s);
        for(int i=1;i<=m;i++) {
            cout<<ask(b[i])<<endl;
        } 
        return 0;
    }
    View Code

    阿狸打字机,最近会做;

    然后谈谈我对后缀数组的小理解,可能会有错误,以后会订正;

    后缀排序;

    反正我也刚学这个东西,后缀自动机学了一点没来得及写题,一说到这里,我就想起来自己线性代数没写,数据结构没写,数论没写,啊啊啊;

    算了,首先后缀数组(SA)是个好东西啊;

    我们用基数排序是在O(n)的时间复杂度内对每个后缀进行排序;

    倍增合并的话是logn的,总的复杂度变成了nlogn,比快排少一个log,还不错;

    就是两个关键字搞来搞去,注释在代码里;

    sa数组表示排名为i的后缀的起始下标;也就是这道题所求的答案;

    x数组是第一关键字,y数组是第二关键字,c数组是桶;

    我们先将x扔进桶里,排好之后将y扔进去;’

    heigh数组表示排名为i的后缀和排名为i-1的后缀的lcp,(最长公共前缀);

    设h[i]=height[rk[i]],同样的,height[i]=h[sa[i]];

    有定理:h[i]>=h[i-1]-1;

    不过这就是我以后写题后再来填坑吧;

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1000010; 
    template<typename T>inline void read(T &x) {
        x=0;
        register int f=1;
        register char ch=getchar();
        while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }
    
    int n,m,c[N],sa[N],x[N],y[N];
    char s[N];
    
    inline void get_sa() {
        m=122;
        for(int i=1;i<=n;i++) c[x[i]=s[i]]++;//建基数排序的桶 ,x[i]为i个字符的第一关键字 
        for(int i=2;i<=m;i++) c[i]+=c[i-1];// 做c的前缀和,为了求出每个关键字最多在第几名; 
        for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
        for(int k=1;k<=n;k=k<<1) {
            int num=0;//一个计数器; 
            for(int i=n-k+1;i<=n;i++) y[++num]=i;//y表示是第二关键字;
            //因为n-k+1位到第n位是空串,空串优先级最高,排名靠前 
            for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
            //如果排名为i的数 在数组中是否大于k;
            //如果(sa[i]>k) 他可以作为第二关键字,直接把它第一关键字的位置添加y即可;
            //这里i枚举的是排名,第二关键字靠前的先进; 
            for(int i=1;i<=m;i++) c[i]=0;//清桶; 
            for(int i=1;i<=n;i++) ++c[x[i]];// 此时x作为第一关键字已经更新过,直接丢尽桶; 
            for(int i=2;i<=m;i++) c[i]+=c[i-1];//第一关键字排名为1-i的个数; 
            for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
            //因为y是按照第二关键字排的,所以第二关键字靠后的,在第一关键字对应的桶中靠后; 
            swap(x,y);//无脑交换 ,利用上次信息倍增向下走; 
            x[sa[1]]=1,num=1;
            for(int i=2;i<=n;i++)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
            if(num==n) break;
            m=num;//此时不需要122了; 
        }
        for(int i=1;i<=n;i++) printf("%d ",sa[i]);
    }
    
    int main() {
    //    freopen("a.in","r",stdin);
    //    freopen("a.out","w",stdout);
        scanf("%s",s+1);
        n=strlen(s+1);
        get_sa();
    //    get_height();
        return 0;
    }

     

    转载于:https://www.cnblogs.com/Tyouchie/p/11182025.html

    展开全文
  • 后缀数组就把两个串拼起来,两串之间末尾添加分隔符,然后扫一遍height数组,判断一下sa[i],sa[i-1]是不是在两个串里,是就更新最大值,否则Continue.刚学后缀数组的时候poj上C++,G++都没问题来着,而且当时那个...

    求两个字符串的最长公共字串。练习模板的题..用后缀数组就把两个串拼起来,两串之间和末尾添加分隔符,然后扫一遍height数组,判断一下sa[i],sa[i-1]是不是在两个串里,是就更新最大值,否则Continue.刚学后缀数组的时候poj上C++,G++都没问题来着,而且当时那个模板还是错的- ...今重写了下结果C++各种RE,G++倒是一次过。

    #include

    #include

    #include

    using namespace std;

    typedef long long ll;

    const int maxn=420000;

    int s[maxn],rs[maxn];

    int sa[maxn],t[maxn],t2[maxn],c[maxn];

    int n,m,k,tt;

    char s1[maxn],s2[maxn];

    int rank[maxn],height[maxn];

    int l1,l2;

    inline int idx(char s)

    {

    return s-'a'+2;

    }

    void getheight(int n)

    {

    int i,j,k=0;

    for (i=0; i<=n; i++) rank[sa[i]]=i;

    for (i=0; i

    {

    if (k) k--;

    int j=sa[rank[i]-1];

    while(s[i+k]==s[j+k]) k++;

    height[rank[i]]=k;

    }

    }

    void build_ss(int m,int n)

    {

    n++;

    int i,*x=t,*y=t2;

    for (int i=0; i

    for (int i=0; i

    for (int i=1; i

    for (int i=n-1; i>=0; i--)

    sa[--c[x[i]]]=i;

    for (int k=1; k<=n; k<<=1)

    {

    int p=0;

    for (i=n-k; i

    for (i=0; i=k) y[p++]=sa[i]-k;

    for (i=0; i

    for (i=0; i

    for (i=1; i

    for (i=n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];

    swap(x,y);

    p=1;

    x[sa[0]]=0;

    for (i=1; i

    x[sa[i]]=(y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k])? p-1 : p++;

    if (p>=n) break;

    m=p;

    }

    }

    bool diff(int x,int y)

    {

    int a=min(x,y);

    int b=max(x,y);

    if (al1) return true;

    return false;

    }

    int main()

    {

    // freopen("in.txt","r",stdin);

    while(~scanf("%s",s1))

    {

    scanf("%s",s2);

    l1=strlen(s1);

    l2=strlen(s2);

    for (int i=0; i

    s[i]=idx(s1[i]);

    s[l1]=0;

    n=l1+1;

    for (int i=0; i

    {

    s[n++]=idx(s2[i]);

    }

    s[n]=1;

    build_ss(128,n);

    getheight(n);

    int ans=0;

    for (int i=2; i

    {

    if (diff(sa[i],sa[i-1]))

    ans=max(ans,height[i]);

    }

    printf("%d\n",ans);

    }

    return 0;

    }

    刚学后缀自动机的话,这题拿来练习也挺合适的。用第一个串构建后缀自动机,之后拿第二个传在自动机上跑一遍,逐字符扫描,当前状态按这个字符向下走的状态非空的话,就转移并且tmp++,否则就沿着失配路径找到第一个可以按当前的字符向下转移的状态并且把tmp更新成now->val+1,找不到的话就回到根节点,tmp赋值成0.每次执行完都用tmp去更新一下最大值ans,第二个传扫完后答案也就出来了。用后缀自动机就正常了-C++,G++都没什么问题,而且毕竟是O(n)的,效率比倍增的SA好多了。

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    typedef long long ll;

    const int maxn=101000*4;

    const int S=26;

    int tot,len;

    int n,m;

    int wtop[maxn];

    int c[maxn];

    int k;

    int ans;

    struct node

    {

    node *par,*go[S];

    int val,id;

    }*tail,*root,que[maxn],*top[maxn];

    char str[maxn],s[maxn],ss[maxn];

    inline int idx(char s)

    {

    return s-'a';

    }

    struct SAM

    {

    void init(int m)

    {

    for (int i=0; i<=m; i++)

    {

    memset(que[i].go,0,sizeof que[i].go);

    que[i].id=que[i].val=0;

    }

    tot=0;

    len=1;

    root=tail=&que[tot++];

    root->id=0;

    ans=0;

    }

    void add(int c,int l)

    {

    node* p=tail;

    node* np=&que[tot++];

    np->val=l;

    np->id=tot-1;

    while(p && p->go[c]==NULL) p->go[c]=np,p=p->par;

    if (p==NULL) np->par=root;

    else

    {

    node *q=p->go[c];

    if (p->val+1==q->val) np->par=q;

    else

    {

    node *nq=&que[tot++];

    *nq=*q;

    nq->id=tot-1;

    nq->val=p->val+1;

    np->par=q->par=nq;

    while(p && p->go[c]==q) p->go[c]=nq,p=p->par;

    }

    }

    tail=np;

    }

    void debug_suff()

    {

    for (int i=0; i

    {

    for (int c=0; c

    if (que[i].go[c])

    {

    cout<id<

    }

    }

    }

    void debug_pre()

    {

    for (int i=1; i

    {

    cout<id<

    }

    }

    void TopS()

    {

    memset(c,0,sizeof c);

    for (int i=0; i

    c[que[i].val]++;

    for (int i=1; i

    c[i]+=c[i-1];

    for (int i=0; i

    top[--c[que[i].val]]=&que[i],wtop[c[que[i].val]]=i;

    }

    int slove(char* s)

    {

    int res=0,tmp=0;

    node *p=root;

    int l=strlen(s);

    for(int i=0; i

    {

    int x=idx(s[i]);

    if (p->go[x])

    {

    p=p->go[x];

    tmp++;

    }

    else

    {

    while(p && p->go[x]==NULL)p=p->par;

    if (p)

    {

    tmp=p->val+1;

    p=p->go[x];

    }

    else

    {

    p=root;

    tmp=0;

    }

    }

    res=max(res,tmp);

    }

    return res;

    }

    }sam;

    char s1[maxn],s2[maxn];

    int main()

    {

    // freopen("in.txt","r",stdin);

    while(~scanf("%s",s1))

    {

    scanf("%s",s2);

    int l1=strlen(s1);

    sam.init(2*l1);

    for (int i=0; i

    sam.add(idx(s1[i]),len++);

    sam.TopS();

    printf("%d\n",sam.slove(s2));

    }

    return 0;

    }

    展开全文
  • 题目: ... 分析: 考虑枚举宽度w,然后把宽度压位集中,将它们哈希 ...这个可以用后缀数组/后缀自动机解决 小技巧:每个连接符用不同的整数表示,那么去做height的时候就不会把连接符包含进去 后缀...
  • 后缀自动机:利用right集合的包含关系,利用一开始的原串的前缀串的最右端,去更新其他点right集合右端点包含它的子串出现的右端点位置,然后用最大位置减去最小位置l【i】的关系看是否有重复#include&...
  • 今天做了场字符串的练习,包括KMP,Trie,AC自动机和后缀数组。 A. Oulipo 貌似是POJ的,以前做过。直接用KMP水过了 。 B. 统计难题 是HDU的吧,题意就是求一些串是另一些串前缀的个数,直接用Trie搞。 struct ...
  • 解法一:后缀数组 听说后缀数组解第k小本质不同的子串是一个经典问题。 把后缀排好序后第i个串的本质不同的串的贡献就是\(n-sa[i]+1-LCP(i,i-1)\)然后我们累加这个贡献,看到哪一个串的时候,这个贡献的大于等于k...
  • 昨天今天主要复习了AC自动机和后缀数组,更深一层的理解倒是没有,只是复习回忆以前的只是,感觉还是停留在入门级别,至于消化理解还是有一定差距,感觉这两天来收获不大,果然在家的效率不高,无心学习,明天静下...
  • 将n个串接到一起,中间用分隔符隔开,然后求长串的后缀数组,解height数组 做过后缀数组的都知道,我们想知道他们中的不同的子串是可以的,但想想这样其实是个暴力的方法,尝试了下果断是TLE的。 但这可以给我们之后...
  • 后缀数组就把两个串拼起来,两串之间末尾添加分隔符,然后扫一遍height数组,判断一下sa[i],sa[i-1]是不是在两个串里,是就更新最大值,否则Continue.刚学后缀数组的时候poj上C++,G++都没问题来着,而且当时那个...
  • 题目大意: ...很明显的一个做法是将S1S2连接起来中间用未出现的字符隔开, 然后建立后缀自动机, 记录每一个状态中表示的字符串的来源(可以状压记录), 然后所有状态中, 满足Right集合为2, 且状压表
  • 解法一:建立后缀数组,对每对sa[i]sa[i+k-1]求lcp,再减去height[i]height[i+k]中较大的那个,即len=lcp(sa[i],sa[i+k-1])-max(height[i],height[i+k]),如果还有剩余则说明由s[sa[i]]的前[1,len]个字母组成的...
  • 第一种做法是把两个字符串接起来,中间放一个奇怪的字符,然后建这个串的后缀数组,求出h数组,对于h[i]表示lcp(sa[i],sa[i-1]),如果sa[i]sa[i-1]分布在奇怪的字符的两边就用h[i]更新答案。。   然后补了...
  • 后缀数组解法:将这n个字符串用一种没有出现的字符作为分隔连在一起求后缀数组,把起始点在第一个字符串中的后缀放在集合A里,把其他的后缀放在集合B里,对于集合A中的每一个后缀,从集合B中找到它名次最接近的一...
  • 这里ac自动机和后缀数组都可以做 当然后缀数组很容易就解决,但是相对时间消耗高 这里就只讲ac自动机了 将每个字符串放入ac自动机中,这里需要记录到达每个ac自动机上的节点出现这个状态有多少次 而我们添加字符...
  • 题解:后缀数组把h数组跑出来,然后线段树维护下,每次查询连续k个后缀的的公共长度,并且不能前一个后一个一样 后缀自动机也可以,学会后再补上 #include<iostream> #include<cstdio> #include&...
  • 题目分析:因为这个公共子串只能在字符串中出现一次,考虑到用后缀数组,我们先将两个字符串通过特殊字符拼接起来,求出后缀数组组后必须满足的一个条件就是height[ i ]必须大于height[ i - 1]height[ i + 1 ]才行...
  • P4000 [Ahoi2013]差异 问题描述 ...还是先说优美的自动机做法,将字符串反过来建立后缀自动机,那么后缀的前缀变成前缀的后缀,那么变成在后缀自动机parent树上求LCA 考虑到所有的LCP要求,那么
  • 传送门 复习了后缀数组。...后缀自动机也是可以的。 因为right集合即为子串在母串中出现位置的右端点的集合,求出right集合就可以确定串的出现位置,那么求出每个点right集合中的最大值最小值,如...
  • 一开始写了一发后缀数组。 T=0的时候直接把所有的n-sa[i]+1-h[i]加到一起一直到K就行了。 T=1时枚举每一位是什么,二分求一下范围,处理一个n-sa[i]+1的前缀。 本来以为会T,结果并没有。。。#include using ...
  • 后缀数组分析:这题的做法论文那题的思想是一样的,就是对于[l,r]区间里的后缀,当一个串i加进去对答案的贡献必须减掉它之前所有串重复的部分。也就是它lcp最大的那个,所以答案就是: 所有的串-重复的串。...
  • 首先第一眼看得出和后缀数组有关, 但是将所有的串连接起来之后, 有一些计数上的细节需要考虑, 首先如果后缀以'0'开头则不需要加入计数(这样的后缀的所有子串对应的整数一定会在其他的后缀当中出现
  • 一直都说自动机后缀树,一直没真正构出后缀树过... 其实建后缀树很简单,父亲边已经有了,关键是边代表的子串怎么求。从叶子一层一层向上,对于节点i,我们已经知道了它在原串的位置逆序后缀长度,他的父亲的...
  • 有一个字符串集合S包含输入的N个字符串,他们的全部字串。 操作字符串很无聊,你决定把它们转化成数字。 你可以把一个字符串转换成一个十进制整数。 如果一个数字出现了多次,只留一个。 计算所有数字的,模...
  • 4199: [Noi2015]品酒大会 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 1391 Solved: 793 [Submit][Status][Discuss] Description 一年一度的“幻影阁夏日品酒...酒家”“首席猎手”两个奖项,吸引了...
  • 学会后缀自动机(SAM)就不用学后缀数组(SA)了?不,虽然SAM看起来更为强大全面,但是有些SAM解决不了的问题能被SA解决,只掌握SAM是远远不够的。  …… 有什么SAM做不了的例子?  比如果求一个串后缀的lcp...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 409
精华内容 163
关键字:

后缀数组和后缀自动机