bzoj3172 luogu3966 [TJOI2013]单词

蒟蒻也能写出来的AC代码！这题是AC自动机模板题。插入单词时用一个没出现过的字符隔开就行了。

一些细节请看注释

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

char a[1000005], b[1000205];//b数组要开这么大，因为要在所有单词拼起来之外再加n个#号

int n, len, mp[205], all, cnt[205];

queue<int> d;

struct ACzdj{

	int siz, s[1000005][26], val[1000005], lst[1000005], fai[1000005];

	int u, v;

	void ins(int k){

		u = 0;

		len = strlen(a);

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

			b[all+i] = a[i];

		all += len;

		b[all++] = '#';

		for(int i=0; i<len; i++){

			v = a[i] - 'a';

			if(!s[u][v])	s[u][v] = ++siz;

			u = s[u][v];

		}

		if(!val[u])	val[u] = k;

		mp[k] = val[u];//mp[k]记录的是与第k号单词相同的单词的最小编号，这样可以解决重复单词。

	}

	void getFail(){

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

			if(s[0][i])

				d.push(s[0][i]);

		while(!d.empty()){

			u = d.front();

			d.pop();

			for(int i=0; i<26; i++){

				v = s[u][i];

				if(v){

					fai[v] = s[fai[u]][i];

					lst[v] = val[fai[v]]?fai[v]:lst[fai[v]];

					d.push(v);

				}

				else	s[u][i] = s[fai[u]][i];

			}

		}

	}

	void query(){

		u = 0;

		for(int i=0; i<all; i++){

			if(b[i]=='#'){

				u = 0;//记得置零

				continue;

			}

			u = s[u][b[i]-'a'];

			if(val[u])	cnt[val[u]]++;

			v = lst[u];

			while(v){

				cnt[val[v]]++;

				v = lst[v];

			}

		}

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

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

	}

}ac;

int main(){

	cin>>n;

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

		scanf("%s", a), ac.ins(i);

	ac.getFail();

	ac.query();

	return 0;

}

巴特西

bzoj3172 luogu3966 [TJOI2013]单词

最新文章

热门文章