結果

問題 No.430 文字列検索
ユーザー ei1333
提出日時 2017-02-23 17:26:12
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 15 ms
コード長 2735 Byte
コンパイル時間 1758 ms
使用メモリ 5292 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt AC 4 ms
1524 KB
challenge02.txt AC 14 ms
5292 KB
challenge03.txt AC 11 ms
2480 KB
challenge04.txt AC 11 ms
2484 KB
sample1.txt AC 3 ms
1520 KB
sample2.txt AC 4 ms
1524 KB
sample3.txt AC 4 ms
1520 KB
sample4.txt AC 3 ms
1524 KB
test1.txt AC 5 ms
1636 KB
test2.txt AC 3 ms
1656 KB
test3.txt AC 4 ms
1580 KB
test4.txt AC 14 ms
3504 KB
test5.txt AC 15 ms
3504 KB
test6.txt AC 14 ms
3504 KB
test7.txt AC 14 ms
3508 KB
test8.txt AC 11 ms
3508 KB
test9.txt AC 11 ms
3504 KB
test10.txt AC 12 ms
3504 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