KMP算法--串的模式比對

題目連接配接：

http://hihocoder.com/problemset/problem/1015?sid=860814

#include <iostream>
#include <vector>
#include<string>
using namespace std;
vector<int> getNext(string& p) {
	int n = p.size();
	vector<int>next(n);
	int k = -1, j = 0; next[0] = -1;
	while (j<n - 1) {
		if (k == -1 || p[j] == p[k]) {
			++j; ++k;
			if (p[j] != p[k])
				next[j] = k;
			else
				next[j] = next[k];
		}
		else k = next[k];
	}
	return next;
}
int kmp(string& s, string& p, vector<int>& next) {
	int slen = s.size(), plen = p.size();
	int i = 0, j = 0, res = 0;
	while (i<slen) {
		if (j == -1 || s[i] == p[j]) {
			++i; ++j;
		}
		else j = next[j];
		if (j >= plen-1) {
			res++;
			j = next[plen-1];
		}
	}
	return res;
}
int main() {
	int num; cin >> num;
	string s, p;
	while (num--) {
		cin >> p >> s;
		p += " ";
		vector<int>next = getNext(p);
		cout << kmp(s, p, next) << endl;
	}
	return 0;
}