SPOJ 8222. Substrings（后缀自动机模板）

后缀自动机+dp。

后缀自动机主要是在functioner大牛那里学习的：http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html

这道题是在No_stop大牛那里学习的：http://blog.csdn.net/no__stop/article/details/11784715

特别感谢这两位大牛！贴上代码作为以后的模板吧。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;

const int N = 550000;

struct suffix_automaton

{

        char s[N];

        int chd[N][26],pre[N],step[N];

        int last,tot;

        inline void rush(int v)

        {

            step[++tot]=v;

            CLR(chd[tot], 0);

        }

        void Extend(int ch)

        {

            rush(step[last]+1);

            int p=last,np=tot;

            for (; !chd[p][ch]; p=pre[p]) chd[p][ch]=np;

            if (!p) pre[np]=1;

            else

            {

                 int q=chd[p][ch];

                 if (step[q]!=step[p]+1)

                 {

                    rush(step[p]+1);

                    int nq=tot;

                    memcpy(chd[nq],chd[q],sizeof(chd[q]));

                    pre[nq]=pre[q];

                    pre[q]=pre[np]=nq;

                    for (; chd[p][ch]==q; p=pre[p]) chd[p][ch]=nq;

                 }  else pre[np]=q;

            }

            last=np;

        }

        void Build()

        {

            scanf("%s", s);

            tot = last = 1;

            CLR(pre,0);CLR(step,0);CLR(chd[1], 0);

            for (int i=0,End=strlen(s); i<End; i++) Extend(s[i]-'a');

        }

        int pos[N], cnt[N], dp[N], g[N];

        void Work()

        {

            Build();

            int len = strlen(s);dp[0] = 0;

            for(int i = 0; i <= len; i ++) cnt[i] = 0;///清零

            for(int i = 1; i <= tot; i ++) cnt[step[i]] ++;///统计长度为step[i]的节点个数。

            for(int i = 1; i <= len; i ++) cnt[i] += cnt[i - 1];///用来hash到（1-tot）。

            for(int i = 1; i <= tot; i ++) pos[cnt[step[i]] --] = i, g[i] = dp[i] = 0;///pos表示长度为step[i]的串位置为i。

            int p = 1;

            for(int i = 0; i < len; i ++) g[p = chd[p][s[i] - 'a']] ++;///顺着串走一遍

            for(int i = tot; i > 0; i --)///反着来，确保right集合可以用pre求个数。

            {

                p = pos[i];///反hash

                dp[step[p]] = max(dp[step[p]], g[p]);

                g[pre[p]] += g[p];///求right集合元素个数。

            }

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

                dp[i] = max(dp[i], dp[i + 1]);

            for(int i = 1; i <= len; i ++)

                printf("%d\n", dp[i]);

        }

}Suf;

int main()

{

    Suf.Work();

}

巴特西

SPOJ 8222. Substrings（后缀自动机模板）

最新文章

热门文章