BZOJ3926 ZJOI2015诸神眷顾的幻想乡（广义后缀自动机）

　　对多串建立SAM的一种方法是建trie再对trie建SAM。构造方式分为在线（也即不建trie而是依次插入每个串，或在trie上dfs）和离线（也即建好trie再bfs）。其中离线构造与单串的构造方式几乎没有区别，将父亲所在节点作为last即可，按bfs序建SAM可以避免出现要转移到的状态已经存在的情况。而在线构造时则需要考虑这点，若存在除了不用新建节点其余操作也与单串区别不大。

　　这种做法相比加分隔符建SAM，一方面避免了存在分隔符的尴尬状态的存在，方便于统计一些东西。（比如本题的本质不同子串数量，如果加分隔符就还要考虑一下right集合，不过好像影响也不是特别大？）另一方面这样建出的SAM总状态数是O(|T|)的，转移函数也即边数是O(|T||A|)的，虽然在线构造的复杂度是O(G(T)+|T||A|)，但更简单的离线构造可以做到理论最低复杂度O(|T||A|)（|T|为trie总节点数，|A|为字符集大小，G(T)为trie上所有叶子深度之和，据论文，我当然啥都不知道）；而加分隔符建SAM的上述所有复杂度都是O(G(T))。也就是说这种做法在直接给出trie的题中会吊打加分隔符。

　　对于本题，如果离线构造，拎出每个叶子作为根得到的trie合并起来建SAM即可。在线构造只要以每个叶子为根dfs并插进SAM。

　　在线：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 4000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

    int x=0,f=1;char c=getchar();

    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

    return x*f;

}

int n,a[N],p[N],degree[N],id[N],son[N][10],fail[N],len[N],t,cnt=1;

ll ans;

struct data{int to,nxt;

}edge[N];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

int ins(int c,int p)

{

    if (son[p][c])

    {

        int q=son[p][c];

        if (len[p]+1==len[q]) return q;

        else

        {

            int y=++cnt;

            len[y]=len[p]+1;

            memcpy(son[y],son[q],sizeof(son[q]));

            fail[y]=fail[q],fail[q]=y;

            while (son[p][c]==q) son[p][c]=y,p=fail[p];

            return y;

        }

    }

    else

    {

        int x=++cnt;len[x]=len[p]+1;

        while (!son[p][c]&&p) son[p][c]=x,p=fail[p];

        if (!p) fail[x]=1;

        else

        {

            int q=son[p][c];

            if (len[p]+1==len[q]) fail[x]=q;

            else

            {

                int y=++cnt;

                len[y]=len[p]+1;

                memcpy(son[y],son[q],sizeof(son[q]));

                fail[y]=fail[q],fail[x]=fail[q]=y;

                while (son[p][c]==q) son[p][c]=y,p=fail[p];

            }

        }

        return x;

    }

}

void dfs(int k,int from)

{

    id[k]=ins(a[k],id[from]);

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from) dfs(edge[i].to,k);

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3926.in","r",stdin);

    freopen("bzoj3926.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();read();

    for (int i=1;i<=n;i++) a[i]=read();

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

    {

        int x=read(),y=read();

        addedge(x,y),addedge(y,x);

        degree[x]++,degree[y]++;

    }

    id[0]=1;

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

    if (degree[i]==1) dfs(i,0);

    for (int i=1;i<=cnt;i++) ans+=len[i]-len[fail[i]];

    cout<<ans;

    return 0;

}

　　离线：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 4000010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,c,a[N],p[N],degree[N],id[N],son[N][10],q[N],trie[N][10],fail[N],len[N],t,cnt;

ll ans;

struct data{int to,nxt;

}edge[N];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

int ins(int c,int p)

{

	int x=++cnt;len[x]=len[p]+1;

	while (!son[p][c]&&p) son[p][c]=x,p=fail[p];

	if (!p) fail[x]=1;

	else

	{

		int q=son[p][c];

		if (len[p]+1==len[q]) fail[x]=q;

		else

		{

			int y=++cnt;

			len[y]=len[p]+1;

			memcpy(son[y],son[q],sizeof(son[q]));

			fail[y]=fail[q],fail[x]=fail[q]=y;

			while (son[p][c]==q) son[p][c]=y,p=fail[p];

		}

	}

	return x;

}

void dfs(int k,int from)

{

	if (!trie[id[from]][a[k]]) trie[id[from]][a[k]]=++cnt;

	id[k]=trie[id[from]][a[k]];

	for (int i=p[k];i;i=edge[i].nxt)

	if (edge[i].to!=from) dfs(edge[i].to,k);

}

void bfs()

{

	int head=0,tail=1;q[1]=0;id[0]=1;cnt=1;

	do

	{

		int x=q[++head];

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

		if (trie[x][i])

		{

			q[++tail]=trie[x][i];

			id[trie[x][i]]=ins(i,id[x]);

		}

	}while (head<tail);

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("bzoj3926.in","r",stdin);

	freopen("bzoj3926.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	n=read(),c=read();

	for (int i=1;i<=n;i++) a[i]=read();

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

	{

		int x=read(),y=read();

		addedge(x,y),addedge(y,x);

		degree[x]++,degree[y]++;

	}

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

	if (degree[i]==1) dfs(i,0);

	bfs();

	for (int i=1;i<=cnt;i++) ans+=len[i]-len[fail[i]];

	cout<<ans;

	return 0;

}

　　离线甚至慢了一倍，可能是要先建trie的原因。

巴特西

BZOJ3926 ZJOI2015诸神眷顾的幻想乡（广义后缀自动机）

最新文章

热门文章