hihocoder #1015 : KMP算法

浏览数：116 / 时间：2015年06月08日

hihocoder.com 上的KMP算法题，搞了半天在VS2012是能通过的，提交上去就是有问题，反复改终于通过了，记录在此，以下是测试通过代码。

输入

第一行一个整数N，表示测试数据组数。

接下来的N^2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。

其中N<=20

输出

对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

样例输入

5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD

样例输出

 1 #include<iostream>
 2 //vs2012里用#include<string>即可，G++非要让用.h，原因是strlen()在G++里定义在string.h头文件里，不常用G++，折腾半天
 3 #include<string.h>using namespace std;
 4 void kmpNext(char* pattern, int m, int* p){
 5     p[0] = 0;
 6     int k = 0;
 7     for(int i = 1; i < m; i++){
 8         while(k > 0 && pattern[k] != pattern[i]){
 9             k = p[k-1];
10         }
11         if(pattern[k] == pattern[i]){
12             p[i] = ++k;
13         }else{
14             p[i] = 0;//k == 0
15         }
16     }
17 }
18 int kmp(char* str, int start, char* pattern, int k, int m, int *p){
19 //     int k = 0;
20     int i = start;
21     while(str[i] != ‘\0‘){
22         while(k > 0 && str[i] != pattern[k]) k = p[k-1];
23         if(str[i] == pattern[k]){
24             k++;
25             if(k == m) return i - m + 1;
26         }
27         i++;
28     }
29     return -1;
30 }
31 int match(char* str, char* pattern, int m, int *p){
32     int ret = 0;
33     int i = 0;
34     int k = 0;
35     while(str[i] != ‘\0‘){
36         int idx = kmp(str, i, pattern, k, m, p);
37         if(idx == -1) break;
38         ret++;
39         k = p[m-1];
40         i = idx + m;
41     }
42     return ret;
43 }
44 int main(){
45     int N;
46     cin >> N;
47     char pattern[10001];
48     char str[1000001];
49     int p[10001];
50     // char *pattern = new char[10001];
51     // char *str = new char[1000001];
52     // int *p = new int[10001];
53     for(int i = 0; i < N; i++){
54         //getline(cin, pattern[i]);
55         //getline(cin, str[i]);
56         cin >> pattern;
57         cin >> str;
58         int m = strlen(pattern);
59         kmpNext(pattern, m, p);
60         int num = match(str, pattern, m, p);
61         cout<<num<<endl;
62     }
63     // delete []pattern;
64     // delete []str;
65     // delete []p;
66 }