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，匹配到了就输出对应的解释。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 char str[];

 int next[];

 void get_next(char* s,int* next)

 {

     int len = strlen(s);

     int i = -,j = ;

     memset(next,,sizeof(next));

     next[] = ;

     while(j < len)

     {

         if(i <  || s[i] == s[j])

         {

             i++;

             next[j+] = i;

         }

         else i = ;

         j++;

     }

 }

 int kmp(char* s,char* t,int* next)

 {

     get_next(t,next);

     int lens = strlen(s);

     int lent = strlen(t);

     int i = ,j = ;

     while(i < lens && j < lent)

     {

         if(s[i] == t[j]) j++;

         else j = next[j];

         i++;

     //    printf("%d %d\n",i,j);

     }

     if(j == lent) return i - lent;  //匹配成功返回开始配对的位置

     else return -;   //匹配失败，返回尾指针

 }

 char temp[][] = {"Apple","iPhone","iPod","iPad","Sony"};

 int main()

 {

     while(scanf("%s",str)!=EOF)

     {

         if(kmp(str,temp[],next)!=-) puts("MAI MAI MAI!");

         if(kmp(str,temp[],next)!=-) puts("MAI MAI MAI!");

         if(kmp(str,temp[],next)!=-) puts("MAI MAI MAI!");

         if(kmp(str,temp[],next)!=-) puts("MAI MAI MAI!");

         if(kmp(str,temp[],next)!=-) puts("SONY DAFA IS GOOD!");

     }

 }