結果

問題 No.430 文字列検索
ユーザー ei1333333ei1333333
提出日時 2017-02-23 17:26:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 2,735 bytes
コンパイル時間 1,544 ms
コンパイル使用メモリ 154,748 KB
実行使用メモリ 6,956 KB
最終ジャッジ日時 2023-08-30 21:30:54
合計ジャッジ時間 2,716 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 11 ms
6,956 KB
testcase_02 AC 6 ms
4,380 KB
testcase_03 AC 5 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 9 ms
5,192 KB
testcase_12 AC 9 ms
5,292 KB
testcase_13 AC 10 ms
5,240 KB
testcase_14 AC 8 ms
5,228 KB
testcase_15 AC 8 ms
5,280 KB
testcase_16 AC 7 ms
5,252 KB
testcase_17 AC 7 ms
5,212 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