Hust oj 1637 水神与Linux（KMP）_综合

水神与Linux

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 62(22 users)

Total Accepted: 24(22 users)

Rating:

Special Judge: No

Description

水神喜欢Linux操作系统，因为Linux系统非常的强大，作为一个文艺的程序员Linux系统是一定要了解的。水神需要在一个文件中查找某一个单词（这个单词可以隐含在其它的单词之中），请同学们帮助一下水神。

Input

第一行为一个整数，表示测试数据的组数。对于每组数据，第一行是一个不包含空格的字符串（长度小于10000），这个字符串作为查找的关键字。接下来输入文件的文本内容（会有多行，每行长度小于10000），以一行单独的“EOF”（不含引号）作为一个文件的结束标志。

Output

每组数据，如果找到某一行包含关键字，那么输出这行的行号及这行的内容，行号占4个字符宽度并且右对齐，行号与这行的内容之间有一个空格。如果这组数据中不包含关键字，输出：“Can not find string: xxx” (不包含引号，xxx为关键字)，每组输出后要求额外的空一行。当运行完需要在最后输出一个额外换行

Sample Input

hahah

EOF

hahah

ha hah

EOF

Sample Output

1 hahah

Can not find string: hahah

习惯KMP，因为我不知道STL里的strstr的时间复杂度，怕超时

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;const int maxn = 505;
const int Inf = 0x3f3f3f;
int Next[maxn];
char a[maxn];
char b[maxn];
char c[maxn];
int len_a,len_b;
int pos;
int t;void get_next(char *b,int *next) //获得next数组
{int i = 0;int j = -1;next[0] = -1;  // 将next[0]初始化为-1while(i < len_b){if(j == -1 || b[i] == b[j]) //如果j == -1或者前缀和后缀相等的话，前缀和后缀都加1{++i;++j;next[i] = j; //给next数组赋值}elsej = next[j];//否则回溯到合适位置}
}int kmp(char *a,char *b)
{int i = 0;int j = 0;while(i < len_a){if(j == -1 || a[i] == b[j]) //如果两个字符串字符相同，则对应位置+1{i++;j++;}elsej = Next[j]; // 否则回溯到合适位置if(j == len_b)return i - len_b + 1;}return -1;
}int main()
{scanf("%d",&t);getchar();while(t--){gets(b);len_b = strlen(b);get_next(b,Next);int index = 0;int flag = 0;while(gets(a)){if(strcmp(a,"EOF") == 0) break;++index;len_a = strlen(a);int ans = kmp(a,b);if(ans != -1){printf("%4d %s\n",index,a);flag = 1;}}if(!flag)printf("Can not find string: %s\n",b);printf("\n");}printf("\n");
}