题解 | #String Matching#

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> GetNextTable(const string& p){
  	//初始化Next[0] = -1——在第一个字符就不匹配时，直接在主串上后移动一格和pattern[0]匹配
    vector<int> Next = {-1};
  
  	//初始情况下令j=Next[i-1];
    int j = -1;
  
    for(int i = 1; i < p.size(); ){
	  
	  	//匹配时的情况 和 j回退到Next[0]=-1时都不匹配时的情况
        if(j == -1 || p[j] == p[i]){
            Next.push_back(j + 1);
            j++;
            i++;
        }
	  	//不匹配则回退j
        else{
            j = Next[j];
        }
    }
    return Next;
}

int KMP_count(string& text, string& pattern, vector<int>& Next){
    int i = 0, j = 0, numOfShift = 0;
    while(i < text.size()){
        if(j == pattern.size()){
            numOfShift++;
            j = 0;
            i -= (pattern.size() - 1);
        }
	  	//在第一个字符就不匹配时，直接在主串上后移动一格和pattern[0]匹配
	  	//在当前位置匹配时则继续往后匹配
        if(text[i] == pattern[j] || j == -1){
            i++;
            j++;
        }
        else{
            j = Next[j];
        }
    }
    if(j == pattern.size()) numOfShift++;
    return numOfShift;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;
    vector<int> next = GetNextTable(pattern);
    cout << KMP_count(text, pattern, next);
    return 0;

}