题解 | #String Matching#

#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

void get_next(const string &t, int *next){
	int i=1, j=0;
	next[1] = 0;
	while(i<=t.size()){
		if(j==0 || t[i] == t[j]){
			i++;j++;
			next[i] = j;
		}else{
			j = next[j];
		}
	}
	return;
}

int KMP_47(const string &s, const string &t, int pos){
	int i = pos;
	int j = 1;
	int next[t.size()];
	get_next(t, next);
	int num = 0;
//	while(i<s.size()&&j<=t.size()) s下标从0开始，t下标从1开始 这是原KMP算法，返回的是第一个匹配到的字串的首位位置
	while(i < s.size()){
		if(j==0 || s[i] == t[j-1]){//t实际下标从0开始 
			i++;j++;
		}else{
			j=next[j];
		}
		if(j-1 == t.size()){//检查“匹配成功”  成功则计数，并“假设为失败”来高效地往后跳 
			num++;
			j = next[j-1];
			i--;
		}
	}
	return num; 
}

int main(){
	string s,t;
	while(cin >> s >> t){
		printf("%d\n",KMP_47(s,t,0));
		s.clear();
		t.clear();
	}
	return 0;
}