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