首页 > 代码库 > HDU 5007 Post Robot KMP (ICPC西安赛区网络预选赛 1001)
HDU 5007 Post Robot KMP (ICPC西安赛区网络预选赛 1001)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5007
解题报告：输入一篇文章，从头开始，当遇到 “Apple”, “iPhone”, “iPod”, “iPad” 这几个字符串时，输出”MAI MAI MAI!“，当遇到"Sony"时，输出“SONY DAFA IS GOOD!"。
看题太渣，题目意思还有个每个单词最多只出现一次关键词。有了这个条件就简单了，只要分别对每个单词进行五次KMP，匹配到了就输出对应的解释。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 char str[1000000]; 7 int next[1000000]; 8 void get_next(char* s,int* next) 9 {10 int len = strlen(s);11 int i = -1,j = 0;12 memset(next,0,sizeof(next));13 next[0] = 0;14 while(j < len)15 {16 if(i < 0 || s[i] == s[j])17 {18 i++;19 next[j+1] = i;20 }21 else i = 0;22 j++;23 } 24 }25 int kmp(char* s,char* t,int* next)26 {27 get_next(t,next);28 int lens = strlen(s);29 int lent = strlen(t);30 int i = 0,j = 0;31 while(i < lens && j < lent)32 {33 if(s[i] == t[j]) j++;34 else j = next[j];35 i++;36 // printf("%d %d\n",i,j);37 }38 if(j == lent) return i - lent; //匹配成功返回开始配对的位置 39 else return -1; //匹配失败，返回尾指针 40 }41 char temp[6][20] = {"Apple","iPhone","iPod","iPad","Sony"};42 int main()43 {44 while(scanf("%s",str)!=EOF)45 {46 if(kmp(str,temp[0],next)!=-1) puts("MAI MAI MAI!");47 if(kmp(str,temp[1],next)!=-1) puts("MAI MAI MAI!");48 if(kmp(str,temp[2],next)!=-1) puts("MAI MAI MAI!");49 if(kmp(str,temp[3],next)!=-1) puts("MAI MAI MAI!");50 if(kmp(str,temp[4],next)!=-1) puts("SONY DAFA IS GOOD!");51 }52 }
HDU 5007 Post Robot KMP (ICPC西安赛区网络预选赛 1001)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。