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

　　

樣例輸出

3 1 3 1 0

　　

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 }

?

轉載于:https://www.cnblogs.com/poweryong/p/4448670.html

總結

以上是生活随笔為你收集整理的hihocoder #1015 : KMP算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。