HDU 3695 Computer Virus on Planet Pandora AC自动机裸题

题目来源：HDU 3695 Computer Virus on Planet Pandora

题意：输入n个字符串 求最后一个字符串有n个字符串中的几种

思路：直接暴力ac自动机

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 5200010;
char s1[maxn], s2[maxn], s3[maxn];
int ans;
struct node
{
	int val;
	node *next[26];
	node *fail;
	node()
	{
		val = 0;
		for(int i = 0; i < 26; i++)
			next[i] = NULL;
		fail = NULL;
	}
};
node *root;

void insert(char *s)
{
	int n = strlen(s);
	node *curr = root;
	for(int i = 0; i < n; i++)
	{
		int c = s[i] - ‘A‘;
		if(curr->next[c] == NULL)
		{
			node *newnode = new node;
			curr->next[c] = newnode;
		}
		curr = curr->next[c];
	}
	curr->val++;
}

void build()
{
	root->fail = NULL;
	queue <node*> Q;
	Q.push(root);
	while(!Q.empty())
	{
		
		node *temp = Q.front();
		node *p = NULL;
		Q.pop();
		for(int i = 0; i < 26; i++)
		{
			if(temp->next[i] == NULL)
				continue;
			if(temp == root)
				temp->next[i]->fail = root;
			else
			{
				p = temp->fail;
				while(p != NULL)
				{
					if(p->next[i] != NULL)
					{
						temp->next[i]->fail = p->next[i];
						break;
					}
					p = p->fail;
				}
				if(p == NULL)
					temp->next[i]->fail = root;
			}
			Q.push(temp->next[i]);
		}
	}
}
void find(char *s)
{
	int n = strlen(s);
	node *p = root;
	for(int i = 0; i < n; i++)
	{
		int c = s[i] - ‘A‘;
		while(p != root && p->next[c] == NULL)
			p = p->fail;
		p = p->next[c];
		if(p == NULL)
			p = root;
		node *temp = p;
		while(temp != root)
		{
			if(temp->val > 0)
			{
				ans += temp->val;
				temp->val = 0;
				temp = temp->fail;
			}
			else break;
		}
	}
}

void del(node *p)
{
	for(int i = 0; i < 26; i++)
	{
		if(p->next[i] != NULL)
			del(p->next[i]);
	}
	free(p);
}

void get()
{
	int len = strlen(s1);
	int sum = 0;
	int flag = 0;
	int l = 0;
	for(int i = 0; i < len; i++)
	{
		if(s1[i] == ‘[‘)
		{
			flag = 1;
			sum = 0;
		}
		else if(s1[i] == ‘]‘)
		{
			;
		}
		else if(flag)
		{
			if(s1[i] >= ‘0‘ && s1[i] <= ‘9‘)
				sum = sum * 10 + s1[i] - ‘0‘;
			else
			{
				flag = 0;
				for(int j = 0; j < sum; j++)
					s2[l++] = s1[i];
			}
		}
		else 
			s2[l++] = s1[i];
	}
	s2[l] = 0;
	s3[l] = 0;
	int j = l;
	for(int i = 0; i < l; i++)
		s3[l-i-1] = s2[i];
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		ans = 0;
		root = new node;
		int n;
		scanf("%d", &n);
		while(n--)
		{
			char s[1111];
			scanf("%s", s);
			insert(s);
		}
		build();
		scanf("%s", s1);
		get();
		find(s2);
		find(s3);
		printf("%d\n", ans);
	}
	return 0;
}

HDU 3695 Computer Virus on Planet Pandora AC自动机裸题,古老的榕树,5-wow.com