首页 > ACM题库 > HDU-杭电 > HDU 3065-病毒侵袭持续中[解题报告]HOJ
2014
03-01

HDU 3065-病毒侵袭持续中[解题报告]HOJ

病毒侵袭持续中

问题描述 :

小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下,他发现了网路中的“万恶之源”。这是一个庞大的病毒网站,他有着好多好多的病毒,但是这个网站包含的病毒很奇怪,这些病毒的特征码很短,而且只包含“英文大写字符”。当然小t好想好想为民除害,但是小t从来不打没有准备的战争。知己知彼,百战不殆,小t首先要做的是知道这个病毒网站特征:包含多少不同的病毒,每种病毒出现了多少次。大家能再帮帮他吗?

输入:

第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。
接下来N行,每行表示一个病毒特征码,特征码字符串长度在1―50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。
在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

输出:

第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。
接下来N行,每行表示一个病毒特征码,特征码字符串长度在1―50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。
在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

样例输入:

3
AA
BB
CC
ooxxCC%dAAAoen....END

样例输出:

AA: 2
CC: 1
Hint
Hit: 题目描述中没有被提及的所有情况都应该进行考虑。比如两个病毒特征码可能有相互包含或者有重叠的特征码段。 计数策略也可一定程度上从Sample中推测。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
typedef long long ll;
#define N 2000009
char a[N];
char str[1009][59];
struct node {
	int cnt;
	node *fail, *next[28];
	node () {
		cnt = 0;
		fail = NULL; memset (next, NULL, sizeof(next));
	}
};
node *root, *que[N];
void add (char a[], int k) {
	node *p = root;
	for (int i = 0; a[i]; ++i) {
		int v = a[i] - 'A';
		if(p->next[v] == NULL) 
			p->next[v] = new node();
		p = p->next[v];
	}
	p->cnt = k;
}

void build () {
	int tail = 0, head =0;
	que[tail++] = root;
	while (head < tail) {
		node *p = que[head++];
		for (int i = 0; i < 28; ++i) {
			if(p ->next[i] != NULL) {
				que[tail++] = p->next[i];
				if(p == root) {
					p->next[i]->fail =root;
				}else {
					node *temp = p->fail;
					p->next[i]->fail = root;
					while (temp != NULL) {
						if(temp->next[i] != NULL) {
							p->next[i]->fail = temp->next[i];
							break;
						}
						temp = temp->fail;
					}
				}
			}
		}
	}
}
struct no {
	char a[59];
	int num;
}pe[10009];
void query(char a[]) {
	node *p = root;
	for (int i = 0; a[i]; ++i) {
		int v = a[i] - 'A';
		if(v > 26 || v < 0) v = 26;
		while(p->next[v] ==NULL && p!= root) {
			p = p->fail;
		}
		p = p->next[v];
		if(p == NULL) p = root;
		node *temp = p;
		while (temp != root ) {
			if(temp->cnt) {
				pe[temp->cnt].num++;
			}
			temp = temp->fail;
		}
	}

}

void cal(node *p) {
	if(p == NULL) return;
	for (int i = 0; i < 27; ++i) 
		if(p->next[i] != NULL) 
			cal(p->next[i]);
	delete p;
}
int cmp(no a, no b) {
	return strcmp(a.a, b.a) < 0;
}
int main () {
	int n;
	while (scanf ("%d", &n) != EOF) {
		root = new node;
		for (int i = 1; i <= n; ++i) {
			scanf ("%s", pe[i].a);
			pe[i].num = 0;
			add(pe[i].a, i);
		}
		build();
		scanf ("%s", a);
		query(a);
		//sort(pe, pe + n, cmp);
		for (int i = 1; i <= n; ++i) {
			if(pe[i].num) 
				printf ("%s: %d\n", pe[i].a, pe[i].num);
		}
		cal(root);
	}
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。