POJ 3461 Oulipo

題意：
    找出W字串在T字串中出現幾次。例如W="AZA",T="AZAZAZA"，答案為3次。

想法：
    套KMP演算法

	#include <iostream>
	#include <string>
	using namespace std;
	string W, T;
	int pi[10001]; // prefix index for W string
	void Compute_pi();
	int KMP();
	int main()
	{
	ios::sync_with_stdio(false);
	int Case;
	cin >> Case;
	while (Case--) {
	cin >> W >> T;
	Compute_pi();
	cout << KMP() << endl;
	}
	}
	void Compute_pi()
	{
	pi[0] = -1;
	for (int q = 1; q < W.size(); ++q) {
	if (W[q] == W[pi[q-1]+1])
	pi[q] = pi[q-1]+1;
	else if (W[q] == W[0])
	pi[q] = 0;
	else
	pi[q] = -1;
	}
	}
	int KMP()
	{
	// q is index of W string, i is index of T string
	int result = 0;
	int q = -1;
	for (int i = 0; i < T.size(); ++i) {
	while (q >= 0 && W[q+1] != T[i])
	q = pi[q];
	if (W[q+1] == T[i])
	++q;
	if (q == W.size()-1) {
	++result;
	q = pi[q];
	}
	}
	return result;
	}

view raw [POJ] 3461 Oulipo.cpp hosted with ❤ by GitHub