結果

問題 No.430 文字列検索
ユーザー lumc_lumc_
提出日時 2018-08-31 13:04:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 2,223 bytes
コンパイル時間 5,039 ms
コンパイル使用メモリ 178,048 KB
実行使用メモリ 7,556 KB
最終ジャッジ日時 2023-10-11 22:47:07
合計ジャッジ時間 3,066 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 16 ms
7,556 KB
testcase_02 AC 6 ms
4,352 KB
testcase_03 AC 5 ms
4,352 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 4 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 13 ms
5,988 KB
testcase_12 AC 14 ms
6,484 KB
testcase_13 AC 14 ms
6,484 KB
testcase_14 AC 10 ms
5,548 KB
testcase_15 AC 8 ms
4,936 KB
testcase_16 AC 7 ms
4,732 KB
testcase_17 AC 8 ms
4,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// never fail to call build() !!
// constructor()
// add(string)
// match(string) : [left, right], vec<tuple<int left, int right, int key>> in
// right-order
/// --- AhoCorasick Library {{{ ///

struct AhoCorasick {
  struct Trie {
    unordered_map< char, Trie* > child;
    Trie* failure = nullptr;
    // vector< int > words;
    int words = 0;
    Trie* add(char c) {
      if(child.count(c)) {
        return child[c];
      } else {
        return child[c] = new Trie;
      }
    }
    Trie* go(char c) {
      if(child.count(c)) {
        return child[c];
      } else {
        if(failure == nullptr) {
          return this;
        } else {
          return failure->go(c);
        }
      }
    }
  };
  Trie* top = new Trie;
  vector< string > dict;
  void add(string word) {
    Trie* now = top;
    for(size_t i = 0; i < word.size(); i++) {
      now = now->add(word[i]);
    }
    now->words++;
    // now->words.emplace_back(dict.size());
    // dict.emplace_back(word);
  }
  void build() {
    queue< Trie* > q;
    q.emplace(top);
    while(q.size()) {
      Trie* now = q.front();
      q.pop();
      for(pair< char, Trie* > ch : now->child) {
        q.emplace(ch.second);
        Trie* failure = ch.second->failure =
          now == top ? top : now->failure->go(ch.first);
        /// only from failure!!
        // vector< int >& words = ch.second->words;
        // words.insert(end(words), begin(failure->words), end(failure->words));
        ch.second->words += failure->words;
      }
    }
  }
  ll match(string s) {
    Trie* now = top;
    // vector< tuple< int, int, int > > res;
    ll res = 0;
    for(size_t i = 0; i < s.size(); i++) {
      now = now->go(s[i]);
      res += now->words;
      // for(int word : now->words) {
      //   res.emplace_back(i - dict[word].size() + 1, i, word);
      // }
    }
    return res;
  }
};

/// }}}--- ///

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  string s; cin >> s;
  int n; cin >> n;
  AhoCorasick ecasd;
  for(int i = 0; i < n; i++) {
    string t; cin >> t;
    ecasd.add(t);
  }
  ecasd.build();
  cout << ecasd.match(s) << endl;
  return 0;
}
0