結果

問題 No.430 文字列検索
ユーザー ei1333
提出日時 2017-02-23 17:26:12
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 15 ms
コード長 2,735 Byte
コンパイル時間 2,349 ms
使用メモリ 6,536 KB
最終ジャッジ日時 2018-03-19 17:46:06

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 2 ms
1,532 KB
challenge02.txt AC 15 ms
6,536 KB
challenge03.txt AC 10 ms
2,476 KB
challenge04.txt AC 10 ms
2,472 KB
sample1.txt AC 2 ms
1,528 KB
sample2.txt AC 2 ms
1,532 KB
sample3.txt AC 2 ms
1,524 KB
sample4.txt AC 2 ms
1,528 KB
test1.txt AC 5 ms
1,644 KB
test2.txt AC 3 ms
1,668 KB
test3.txt AC 2 ms
1,588 KB
test4.txt AC 14 ms
3,496 KB
test5.txt AC 14 ms
3,496 KB
test6.txt AC 14 ms
3,496 KB
test7.txt AC 13 ms
3,496 KB
test8.txt AC 12 ms
3,496 KB
test9.txt AC 11 ms
3,496 KB
test10.txt AC 11 ms
3,500 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>

using namespace std;

struct TrieNode
{
  int nxt[27];

  int exist, accept;

  TrieNode() : exist(0), accept(0)
  {
    memset(nxt, -1, sizeof(nxt));
  }
};

struct Trie
{
  vector< TrieNode > nodes;

  Trie()
  {
    nodes.push_back(TrieNode());
  }

  virtual void direct_action(int node, int id) {}

  virtual void child_action(int node, int child, int id) {}

  void update_direct(int node, int id)
  {
    ++nodes[node].accept;
    direct_action(node, id);
  }

  void update_child(int node, int child, int id)
  {
    ++nodes[node].exist;
    child_action(node, child, id);
  }

  void add(const string &str, int str_index, int node_index, int id)
  {
    if(str_index == str.size()) {
      update_direct(node_index, id);
    } else {
      const int c = str[str_index] - 'A';
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(TrieNode());
      }
      add(str, str_index + 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(const string &str, int id)
  {
    add(str, 0, 0, id);
  }

  void add(const string &str)
  {
    add(str, nodes[0].exist);
  }

  int size()
  {
    return (nodes[0].exist);
  }

  int nodesize()
  {
    return ((int) nodes.size());
  }
};

struct Aho_Corasick : Trie
{
  static const int FAIL = 26;
  vector< int > correct;

  Aho_Corasick() : Trie() {}

  void build()
  {
    correct.resize(nodes.size());
    for(int i = 0; i < nodes.size(); i++) {
      correct[i] = nodes[i].accept;
    }

    queue< int > que;
    for(int i = 0; i < 27; i++) {
      if(~nodes[0].nxt[i]) {
        nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;
        que.emplace(nodes[0].nxt[i]);
      } else {
        nodes[0].nxt[i] = 0;
      }
    }
    while(!que.empty()) {
      TrieNode &now = nodes[que.front()];
      correct[que.front()] += correct[now.nxt[FAIL]];
      que.pop();
      for(int i = 0; i < 26; i++) {
        if(now.nxt[i] == -1) continue;
        int fail = now.nxt[FAIL];
        while(nodes[fail].nxt[i] == -1) {
          fail = nodes[fail].nxt[FAIL];
        }
        nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];
        que.emplace(now.nxt[i]);
      }

    }
  }

  int move(const string &str, int now = 0)
  {
    int ret = 0;
    for(auto &c : str) {
      while(nodes[now].nxt[c - 'A'] == -1) now = nodes[now].nxt[FAIL];
      now = nodes[now].nxt[c - 'A'];
      ret += correct[now];
    }
    return (ret);
  }
};

int main()
{
  string S;
  int M;

  cin >> S;
  cin >> M;

  Aho_Corasick aho;
  for(int i = 0; i < M; i++) {
    string T;
    cin >> T;
    aho.add(T);
  }
  aho.build();
  cout << aho.move(S) << endl;
}
0