- 浏览: 121812 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
leelege:
让一切GenericDao都去死吧
自己写的一个Hibernate CURD的封装 -
liuxuejin:
不用泛型的飘过,个人觉得没有什么必要,因为增删查的代码(简单的 ...
自己写的一个Hibernate CURD的封装 -
java113096:
finallygo 写道icanfly 写道ricoyu 写道 ...
自己写的一个Hibernate CURD的封装 -
jiluo093:
http://jiluo093.iteye.com/blog/ ...
自己写的一个Hibernate CURD的封装 -
piao_bo_yi:
Dev|il 写道yin_bp 写道Dev|il 写道dnst ...
自己写的一个Hibernate CURD的封装
病毒侵袭
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2557 Accepted Submission(s): 667
Problem Description
当太阳的光辉逐渐被月亮遮蔽,世界失去了光明,大地迎来最黑暗的时刻。。。。在这样的时刻,人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观,那是多么幸福的事儿啊~~
但网路上总有那么些网站,开始借着民众的好奇心,打着介绍日食的旗号,大肆传播病毒。小t不幸成为受害者之一。小t如此生气,他决定要把世界上所有带病毒的网站都找出来。当然,谁都知道这是不可能的。小t却执意要完成这不能的任务,他说:“子子孙孙无穷匮也!”(愚公后继有人了)。
万事开头难,小t收集了好多病毒的特征码,又收集了一批诡异网站的源码,他想知道这些网站中哪些是有病毒的,又是带了怎样的病毒呢?顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦,所以解决问题越快越好哦~~
Input
第一行,一个整数N(1<=N<=500),表示病毒特征码的个数。
接下来N行,每行表示一个病毒特征码,特征码字符串长度在20—200之间。
每个病毒都有一个编号,依此为1—N。
不同编号的病毒特征码不会相同。
在这之后一行,有一个整数M(1<=M<=1000),表示网站数。
接下来M行,每行表示一个网站源码,源码字符串长度在7000—10000之间。
每个网站都有一个编号,依此为1—M。
以上字符串中字符都是ASCII码可见字符(不包括回车)。
Output
依次按如下格式输出按网站编号从小到大输出,带病毒的网站编号和包含病毒编号,每行一个含毒网站信息。
web 网站编号: 病毒编号 病毒编号 …
冒号后有一个空格,病毒编号按从小到大排列,两个病毒编号之间用一个空格隔开,如果一个网站包含病毒,病毒数不会超过3个。
最后一行输出统计信息,如下格式
total: 带病毒网站数
冒号后有一个空格。
Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
Sample Output
web 1: 1 2 3
total: 1
用kmp和trie树都超时
kmp代码:
#include <iostream> using namespace std; int next[501][205]; char web[10001][10005]; char code[501][205]; void getNext(char c[], int cns) { int len = strlen(c); int i = 0, j = -1; next[cns][0] = -1; while(i < len) { if(j == -1 || c[i] == c[j]) { i++; j++; if(c[i] == c[j]) next[cns][i] = next[cns][j]; else next[cns][i] = j; }else j = next[cns][j]; } } bool kmp(char w[], char c[], int cns) { int i = 0, j = 0; int wlen = strlen(w), clen = strlen(c); while(i < wlen && j < clen) { if(j == -1 || w[i] == c[j]) { i++; j++; }else j = next[cns][j]; } if(j == clen) return true; return false; } int main() { int n, m, i, j, total; bool flag; while(cin>>n) { for(i = 0; i < n; i++) { cin>>code[i]; getNext(code[i], i); } cin>>m; total = 0; for(i = 0; i < m; i++) { cin>>web[i]; flag = true; for(j = 0; j < n; j++) { if(kmp(web[i], code[j], j)) if(flag) { cout<<"web "<<i + 1<<":"<<" "<<j + 1; total++; flag = false; } else cout<<" "<<j + 1; } if(!flag) cout<<endl; } cout<<"total: "<<total<<endl; } return 0; }
trie树代码:
#include <iostream> using namespace std; const int branch = 100; char code[205]; char web[10005]; bool flag; int total; typedef struct trie_node{ bool isword; bool isMatch; int rank; struct trie_node *next[branch]; trie_node():isword(false), rank(0), isMatch(false) { memset(next, NULL, sizeof(next)); } }*pTrie_Node; class Trie{ private: pTrie_Node root; public: Trie() { root = new trie_node(); } pTrie_Node getRoot() { return root; } void insert(const char *word, int r); void destory(pTrie_Node cur); void search(const char *word, int r); void clear(pTrie_Node cur); }; void Trie::insert(const char *word, int r) { pTrie_Node loc = root; while(*word && loc) { if(loc->next[*word - 31] == NULL) loc->next[*word - 31] = new trie_node(); loc = loc->next[*word - 31]; word++; } loc->isword = true; loc->rank = r; } void Trie::destory(pTrie_Node cur) { for(int i = 0; i < branch; i++) if(cur->next[i] != NULL) destory(cur->next[i]); delete cur; } void Trie::search(const char *word, int r) { pTrie_Node loc = root; while(*word && loc) { loc = loc->next[*word - 31]; if(loc && loc->isword && !loc->isMatch) { if(flag) { cout<<"web "<<r<<":"<<" "<<loc->rank; total++; flag = false; }else cout<<" "<<loc->rank; loc->isMatch = true; } word++; } } void Trie::clear(pTrie_Node cur) { for(int i = 0; i < branch; i++) if(cur->next[i] != NULL) clear(cur->next[i]); if(cur->isword) cur->isMatch = false; } int main() { int n, m, i, j, len; while(cin>>n) { Trie t; for(i = 1; i <= n; i++) { cin>>code; t.insert(code, i); } cin>>m; total = 0; for(i = 1; i <= m; i++) { flag = true; cin>>web; len = strlen(web); for(j = 0; j < len; j++) { t.search(&web[j], i); } t.clear(t.getRoot()); if(!flag) cout<<endl; } cout<<"total: "<<total<<endl; t.destory(t.getRoot()); } return 0; }
发表评论
-
求n个元素集合的子集(幂集)或n个元素的组合
2011-10-21 13:19 3122回溯法是设计递归过程的一种重要方法,它的求解过程是遍历一个状态 ... -
螺旋矩阵
2011-10-19 13:26 957给一个正整数n,输出一个n*n的螺旋矩阵 螺旋矩阵可以是逆时针 ... -
HDU 2203(亲和串)
2011-09-26 13:10 1046亲和串 Time Limit: 3000/1000 MS (J ... -
HDU2060(Snooker)
2011-09-17 19:20 866Snooker Time Limit: 1000/1000 M ... -
HDU1166(敌兵布阵)
2011-09-17 12:55 803敌兵布阵 Time Limit: 2000/1000 MS ( ... -
HDU1754 I Hate It
2011-09-16 23:40 1023参考资料:http://www.cppblog.com/MiY ... -
HDU1686Oulipo
2011-09-14 22:15 805Oulipo Time Limit: 3000/1000 MS ... -
HDU2100Lovekey
2011-09-12 17:16 690Lovekey Time Limit: 3000/1000 M ... -
HDU3368 Reversi(黑白棋)
2011-09-11 23:04 1028Reversi Time Limit: 5000/2000 M ... -
HDU1010Tempter of the Bone
2011-09-11 23:02 524Tempter of the Bone Time Limit: ... -
求一个集合的全排列
2011-09-11 14:49 775#include <iostream> usin ... -
HDU1175连连看
2011-09-09 23:24 753连连看 Time Limit: 20000/10000 MS ... -
HDU1711Number Sequence
2011-09-09 13:09 713Number Sequence Time Limit: 100 ... -
串的模式匹配算法
2011-09-07 14:01 648c实现 #include <iostream> ... -
HDU1097A hard puzzle
2011-09-06 22:46 819A hard puzzle Time Limit: 2000/ ... -
串的顺序实现
2011-09-06 11:26 819串的顺序实现 串的顺序结构实现有弊端: 1.串的最大长度固定 ... -
HDU1004Let the Balloon Rise
2011-09-06 09:44 509Let the Balloon Rise Time Limit ... -
HDU2061Treasure the new start, freshmen!
2011-08-24 14:06 986Treasure the new start, freshme ... -
HDU2251Seinfeld
2011-08-24 13:39 876Seinfeld Time Limit: 2000/1000 ... -
HDU2083简易版之最短距离
2011-08-22 15:30 892简易版之最短距离 Time Limit: 1000/1000 ...
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码