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 long25 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\n",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 }