当前位置： 移动技术网 > IT编程>开发语言>C/C++ > WA自动鸡

WA自动鸡

2018年03月29日  | 移动技术网IT编程  | 我要评论

哈票网 上海,恶魔王子饲养法则,广告狂人下载

WA鸡

不信啊，你交交试试。

Trie树+next数组。 

WA模板。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int size,sumsize;
struct AC
{
	int son[1000001][30];
	int last[1000001];
	int fail[1000001];
	int back[1000001];
	void clear()
	{
		memset(son[0],0,sizeof(son[0]));
		size=1;
	}
	void clear_x(int x)
	{
		memset(son[x],0,sizeof(son[x]));
		back[x]=0;
	}
	void insert(char *a)
	{
		int len=strlen(a);
		int now=0;
		for(int i=0;i<len;i++)
		{
			int c=a[i]-'a';
			if (!son[now][c]) 
			{
				clear_x(size);
				son[now][c]=size++;
			}
			now=son[now][c];
		}
		back[now]++;
	}
	void gf()
	{
		queue<int> q;
		int u=0;
		fail[0]=0;
		for(int i=0;i<sumsize;i++)
		{
			 u=son[0][i];
			if (u)
			{
				q.push(u);fail[u]=0;last[u]=0;
			}
		}
		while(!q.empty())
		{
			int f=q.front();
			q.pop();
			for(int i=0;i<sumsize;i++)
			{
				 u=son[f][i];
				if (!u)
				{
					son[f][i]=son[fail[f]][i]; continue;
				}
				q.push(u);
				int v=fail[f];
				while(v&&!son[v][i]) v=fail[v];
				fail[u]=son[v][i];
				last[u]=back[fail[u]]?fail[u]:last[fail[u]];
			}
		}
	}
	int find(char *a)
	{
		int u=0,cnt=0;
		int len=strlen(a);
		for(int i=0;i<len;i++)
		{
			int c=a[i]-'a';
			u=son[u][c];
			int tmp=0;
			if (back[u])tmp=u;
			else if (last[u]) tmp=last[u];
			while(tmp)
			{
				cnt+=back[tmp];
				back[tmp]=0;
				tmp=last[tmp];
			}
		}
		return cnt;
	}
}WA;	
char s[1000001];
int n;
int main()
{
	int t;sumsize=27;
	scanf("%d",&t);
	while(t--)
	{
		WA.clear();
		scanf("%d",&n);
	    for(int i=1;i<=n;i++)
		{
			scanf("%s",s);
            WA.insert(s);
		}
		WA.gf();
		scanf("%s",s);
		printf("%d\n",WA.find(s));
		return 0;
	}
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网