【BZOJ 3172】[TJOI 2013]単語(ACオートマチックの小さな応用)

ここをクリックして問題を見る
あなたにN N N個の単語をあげて、それぞれの単語がこのN N個の単語の中で現れる回数を求めてください.

関連テーマ

この問題は洛谷の上の板の問題のアップグレード版であるべきだ.
L i n k Link Link
【洛谷3796】【テンプレート】ACオートマトン(補強版)の問題解詳しくはブログ【洛谷3796】【テンプレート】ACオートマトン(補強版)を参照

A C AC自動機

これはA C AC自動機の簡単な運用問題です.
L i n k Link Link
A C AC自動機詳細はブログ初学AC自動機を参照

問題解

1つの比較的に暴力的なやり方は、このN N個の単語を1本のT r i e Trie Trieを建てて、それから各単語を1つずつA C AC ACオートマチックを走って、残念ながらこのようにT L E TLE TLE TLEになります.
さらに、同じ単語がA C ACオートマチックを走る結果は同じで、なぜ一緒に走らないのかを発見することができます.これでA C ACができます.

コード#コード#

#include
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define tc() (A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++)
#define pc(ch) (pp_<100000?pp[pp_++]=ch:(fwrite(pp,1,100000,stdout),pp[(pp_=0)++]=ch))
#define N 200
#define SUM 1000000
int pp_=0;char ff[100000],*A=ff,*B=ff,pp[100000];
using namespace std;
int n,rt=1,tot=1,ans,s[N+5];
string ss[N+5];
struct Trie
{
	int Son[26],Next,Cnt,Vis;
}node[SUM+5];
queue<int> q;
inline void read(int &x)
{
	x=0;static char ch;
	while(!isdigit(ch=tc()));
	while(x=(x<<3)+(x<<1)+ch-48,isdigit(ch=tc()));
}
inline void read_string(string &x)
{
	x="";static char ch;
	while(isspace(ch=tc()));
	while(x+=ch,!isspace(ch=tc())) if(!(~ch)) return;
}
inline void write(int x)
{
	if(x>9) write(x/10);
	pc(x%10+'0');
}
inline void Insert(int pos,string st)
{
	register int i,nxt,x=rt,len=st.length();
	for(i=0;i<len;++i)
	{
		if(!node[x].Son[nxt=st[i]-97]) node[x].Son[nxt]=++tot;
		x=node[x].Son[nxt];
	}
	++node[x].Cnt,s[pos]=x;
}
inline void GetNext()
{
	register int i,k;q.push(rt);
	while(!q.empty())
	{
		k=q.front(),q.pop();
		for(i=0;i<26;++i)
		{
			if(k^rt)
			{
				if(!node[k].Son[i]) node[k].Son[i]=node[node[k].Next].Son[i];
				else node[node[k].Son[i]].Next=node[node[k].Next].Son[i],q.push(node[k].Son[i]);
			}
			else 
			{
				if(!node[k].Son[i]) node[k].Son[i]=rt;
				else node[node[k].Son[i]].Next=rt,q.push(node[k].Son[i]);
			}
		}
	}
}
inline void AC_Automation(string st,int val)// st AC ， val st 
{
	register int i,j,x=rt,len=st.length();
	for(i=0;i<len;++i)
	{
		if(!(x=node[x].Son[st[i]-97])) {x=rt;continue;}
		int p=x;
		while(p^rt) node[p].Vis+=val,p=node[p].Next;// val 
	}
}
int main()
{
	register int i,j;
	for(read(n),i=1;i<=n;++i) read_string(ss[i]),Insert(i,ss[i]);
	for(GetNext(),i=1;i<=n;++i) 
		if(~node[s[i]].Cnt) AC_Automation(ss[i],node[s[i]].Cnt),node[s[i]].Cnt=-1;// AC ， ， TLE
	for(i=1;i<=n;++i) write(node[s[i]].Vis),pc('
');// Trie 
	return fwrite(pp,1,pp_,stdout),0;
}