3461 Oulipo
問題概要
二つの文字列W,Tが与えられる。
Tの中にWが何回出現するかを数えよ。
Tの長さは1000000以下、Wの長さは10000以下である。
解法
単純に文字列比較を繰り返すと、O(nm)かかってTLE.
KMPなどの文字列検索アルゴリズムを使うと間に合う。
ソースコード
KMPの部分はspaghetti sourceからお借り。
int n,fail[10002]; char W[10000],T[1000000]; void buildFail(char *p) { int m = strlen(p); int j = fail[0] = -1; for (int i = 1; i <= m; ++i) { while (j >= 0 && p[j] != p[i-1]) j = fail[j]; fail[i] = ++j; } } int match(char *t, char *p) { int n = strlen(t), m = strlen(p); int count = 0; for (int i = 0, k = 0; i < n; ++i) { while (k >= 0 && p[k] != t[i]) k = fail[k]; if (++k >= m) { ++count; // match at t[i-m+1 .. i] k = fail[k]; } } return count; } int main() { scanf("%d ",&n); rep(i,n){ gets(W); gets(T); buildFail(W); printf("%d\n",match(T,W)); } return 0; }