1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
using namespace std;
int *getNext(string pattern){
    int size = pattern.length();
    int *next = new int[size];
    next[0] = 0;
    int j = 0;//之前一个next
    for(int i = 1;i<size;i++){
        while(j>=1&&pattern[j]!=pattern[i]){//寻找匹配最大前缀
            j = next[j-1];
        }
        if(pattern[j]==pattern[i]){
            j++;
            next[i] = j;
        }else//未匹配到
            next[i] = 0;
    }
    return next;
}
/************************************************************************/
/* 返回匹配的次数                                                                     */
/************************************************************************/
int matchNum(string s, string pattern){
    int result = 0;
    int *next = getNext(pattern);
    int p = 0;//p为当前要匹配的
    for(int i = 0;i<s.length();i++){
        while(p>0 && s[i]!=pattern[p]){//包含p==pattern.length()的情况
            p = next[p-1];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX