LOJ-1255 : Substring Frequency

問題概要

文字列Sに部分文字列Tがいくつ含まれるか数える問題。KMPやZ-algorithmの検証用。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_L = (int)(1e6);

char S[MAX_L + 1], T[MAX_L + 1], buf[2*MAX_L + 2];

void init() {
	scanf(" %s %s ", S, T);
}

int solve() {
	int sLen = strlen(S), tLen = strlen(T);
	for (int i = 0; i < tLen; ++i) {
		buf[i] = T[i];
	}
	buf[tLen] = '$';
	for (int i = 0; i < sLen; ++i) {
		buf[i+tLen+1] = S[i];
	}
	buf[sLen + tLen + 1] = '\0';

	vector<int> Z;
	buildLongestPrefixMatch(buf, Z);
	return count(Z.begin(), Z.end(), tLen);
}

int main() {
	int T;
	scanf("%d", &T);
	for (int i = 0; i < T; ++i) {
		init();
		printf("Case %d: %d\n", i + 1, solve());
	}
	return 0;
}