题意：找文本串中模式串的个数
解题思路：裸KMP
解题代码：
1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 char str[1005]; 28 char str1[1005]; 29 int next[1005]; 30 void getnext() 31 { 32 int len = strlen(str); 33 next[0] = -1; 34 int k = -1; 35 int j = 0 ; 36 int sum = 0 ; 37 while(j <= len - 1) 38 { 39 if(k == -1 || str[j] == str[k]) 40 { 41 ++j; 42 ++k; 43 next[j] = k ; 44 } 45 else { 46 k = next[k]; 47 } 48 } 49 50 } 51 void kmp() 52 { 53 getnext(); 54 int lstr1 = strlen(str1); 55 int lstr = strlen(str); 56 int i = 0 ; 57 int j = 0 ; 58 int sum = 0 ; 59 while(j < lstr1) 60 { 61 if(i == -1 || str1[j] == str[i]) 62 { 63 i ++ ; 64 j ++; 65 }else{ 66 i = next[i]; 67 } 68 if(i == lstr) 69 { 70 sum ++ ; 71 } 72 } 73 printf("%d ",sum); 74 } 75 int main(){ 76 while(scanf("%s",str1) != EOF) 77 { 78 if(strlen(str1) == 1 && str1[0] == '#') 79 { 80 break; 81 } 82 scanf("%s",str); 83 kmp(); 84 } 85 86 return 0; 87 }