题解 | #String Matching#

#include<iostream>
#include<string>
using namespace std;
int nextable[1000];

void getnext(string a, int n1)
{
	int j = 0;
	nextable[j] = -1;
	int i = nextable[j];
	while (j < n1)
	{
		if (i == -1 || a[i] == a[j])
		{
			i++;
			j++;
			nextable[j] = i;
		}
		else i = nextable[i];
	}
	return;
}

int KMP(string a, string b, int m, int n)
{
	int i = 0;
	int j = 0;
	int num = 0;
	getnext(b, n);
	while (j < m )
	{
		if (i == -1 || a[j] == b[i])
		{
			i++;
			j++;
		}
		else
		{
			i = nextable[i];
		}
		if (i == n)
		{
			num++;
			i = nextable[i];
		}
	}
	return num;
}
int main()
{
	string s1, s2;
	while (cin >> s1 >> s2)
	{
		int m = s1.size();
		int n = s2.size();
		cout << KMP(s1, s2, m, n) << endl;
	}
	return 0;
}