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; }