4502: 串

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 195 Solved: 95
[Submit][Status][Discuss]

Description

兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字

符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合S中某个字符串的前缀。

比如对于字符串集合{"abc","bca"}，字符串"abb"，"abab"是“好”的（"abb"="ab"+"b",abab="ab"+"ab"），而字符串“bc”不是“好”的。

兔子们想知道，一共有多少不同的“好”的字符串。

Input

第一行一个整数n，表示字符串集合中字符串的个数

接下来每行一个字符串

Output

一个整数，表示有多少不同的“好”的字符串

Sample Input

2
ab
ac

Sample Output

HINT

1<=n<=10000，每个字符串非空且长度不超过30，均为小写字母组成。

Source

颂魔和毒爷把这道题加强了一下$\sum S \le 10^6$，然后给了一个更容易的做法。我偷一发题解.....

BZOJ 4502: 串 AC自动机-LMLPHP

正解大概是讲：先钦定一个串C，只在最右边分割点统计。对于{S}中两前缀A,B。定义(A,B)合法仅当不存在划分B的一个前缀，接到A后面得到的(A',B')。那么就考虑一对(A,B)是否合法。

先枚举B，然后再统计多少A后面可以接B的前缀。这里是可以接，而不是接多少次，所以直接用最短的前缀其判断。

这个最短的另一个要求是B'也存在{S}集中。所以可以等价于求一个最长的B'。就是找一个最长的B的后缀，这个可以用fail树求出。

由B'就定位B的最短前缀（Trie树定位），然后就统计它是{S}多少个A‘的后缀（用fail树统计）。

无声PPT

Code

#include< cstdio >

#include< cstring >

#define gec getchar

#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)

#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__)

typedef long long ll;

template

inline void read(T &x)

{

	x=0;bool f=0;char c=gec();

	for(;c<'0'||c>'9';c=gec())f=(c=='-');

	for(;c>='0'&&c<='9';c=gec())x=x*10+c-'0';

	x=f?-x:x;

}

const int MAXN(1000010);

int Case,n,leng; char str[MAXN];

ll Ans;

namespace ACmaton

{

	struct ACtrie

	{

		int nx[26],fail,sum,Dep;

	}trie[MAXN];int ktot=1,root=1;

	void ins()

	{

		int k=1;

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

		{

			if(!trie[k].nx[str[i]-'a'])trie[k].nx[str[i]-'a']=++ktot;

			trie[trie[k].nx[str[i]-'a']].Dep=trie[k].Dep+1;

			k=trie[k].nx[str[i]-'a'];

		}

	}

	int que[MAXN],l,h,now;

	void BFS()

	{

		for(int v=0;v<26;v++)

		if(trie[root].nx[v])

		{

			trie[trie[root].nx[v]].fail=root;

			que[++l]=trie[root].nx[v];

		}else trie[root].nx[v]=root;

		while(h<l)

		{

			now=que[++h];

			for(int v=0;v<26;v++)

			if(trie[now].nx[v])

			{

				trie[trie[now].nx[v]].fail=trie[trie[now].fail].nx[v];

				que[++l]=trie[now].nx[v];

			}else trie[now].nx[v]=trie[trie[now].fail].nx[v];

		}

	}

	int p[MAXN],cnt[MAXN];

	void Pretreat()

	{

		for(int i=1;i<=ktot;i++)cnt[trie[i].Dep]++;

		for(int i=1;i<=ktot;i++)cnt[i]+=cnt[i-1];

		for(int i=ktot;i>=1;i--)p[cnt[trie[i].Dep]--]=i;

		for(int i=ktot;i>=1;i--)

		{

			trie[p[i]].sum++;

			trie[trie[p[i]].fail].sum+=trie[p[i]].sum;

		}

		trie[root].sum=1;

	}

	int st[MAXN],tp;

	void Dfs(int x)

	{

		st[++tp]=x;

		for(int v=0;v<26;v++)

		if(trie[trie[x].nx[v]].Dep==trie[x].Dep+1)Dfs(trie[x].nx[v]);

		int Pre=trie[x].Dep-trie[trie[x].fail].Dep;

		tp--;if(trie[x].fail!=root)Ans-=trie[st[Pre+1]].sum-1;//保留本身一个

	}

}using namespace ACmaton;

int main()

{

	FILE("string");

	read(Case);

	read(n);

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

	{

		scanf("%s",str+1);leng=strlen(str+1);

		ins();

	}

	Ans=((ll)ktot-1ll)*(ktot-1);

	BFS();

	Pretreat();

	Dfs(root);

	printf("%lld\n",Ans);

	return 0;

}

ABB

BZOJ 4502: 串 AC自动机