結果

問題 No.430 文字列検索
コンテスト
ユーザー 193s
提出日時 2017-05-16 20:49:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 677 ms / 2,000 ms
コード長 1,654 bytes
コンパイル時間 682 ms
コンパイル使用メモリ 84,024 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:15:25
合計ジャッジ時間 7,930 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

#define MAX_N 12

int to[MAX_N][26];
int term[MAX_N], len[MAX_N], link[MAX_N], sz;
struct AhoCorasick {
  AhoCorasick() {
    rep(i, MAX_N) {
      rep(c, 26) to[i][c] = 0;
    }
    sz = 1;
  }
  void add_str(string s) {
    int cur = 0;
    for (char c : s) {
      if (!to[cur][c-'A']) {
        to[cur][c-'A'] = sz++;
        len[to[cur][c-'A']] = len[cur] + 1;
      }
      cur = to[cur][c-'A'];
    }
    term[cur] = cur;
  }

  void push_links() {
    int que[sz];
    int st = 0, fi = 1;
    que[0] = 0;
    while (st < fi) {
      int V = que[st++];
      int U = link[V];
      if (!term[V]) term[V] = term[U];
      for (int c=0; c<26; c++) {
        if (to[V][c]) {
          link[to[V][c]] = V ? to[U][c] : 0;
          que[fi++] = to[V][c];
        }
        else {
          to[V][c] = to[U][c];
        }
      }
    }
  }
};

string S;
int M;

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> S >> M;
  int ctr = 0;
  rep(i, M) {
    string s;
    cin >> s;
    AhoCorasick aho;
    aho.add_str(s);
    aho.push_links();

    int cur = 0;
    for (char c : S) {
      cur = to[cur][c-'A'];
      if (cur == s.length()) ctr++;
    }
  }

  cout << ctr << "\n";
  return 0;
}
0