結果

問題 No.430 文字列検索
コンテスト
ユーザー firiexp
提出日時 2020-02-21 23:42:23
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,311 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 770 ms
コンパイル使用メモリ 95,740 KB
最終ジャッジ日時 2024-11-10 00:41:06
合計ジャッジ時間 1,165 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In instantiation of 'struct AhoCorasick<26, 65>::Node':
main.cpp:90:35:   required from here
main.cpp:27:23: error: 'AhoCorasick<W, start>::Node::to' has incomplete type
   27 |         array<int, W> to;
      |                       ^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_map.h:63,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/map:61,
                 from main.cpp:5:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/tuple:1595:45: note: declaration of 'struct std::array<int, 26>'
 1595 |   template<typename _Tp, size_t _Nm> struct array;
      |                                             ^~~~~

ソースコード

diff #
raw source code 

#include <limits>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>
#include <cassert>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<int W, int start>
class AhoCorasick {
public:
    struct Node {
        array<int, W> to;
        int fail;
        int val;
    };
    explicit AhoCorasick() : v(1) {}
    vector<Node> v;
    vector<int> ord;
    int add(string &s, int x = 0, int cur = 0){
        for (auto &&i : s) {
            if(!v[cur].to[i-start]) v[cur].to[i-start] = v.size(), v.emplace_back();
            cur = v[cur].to[i-start];
        }
        return cur;
    }

    void build() {
        v[0].fail = -1;
        int l = 0, r = 1;
        ord.clear();
        ord.reserve(v.size());
        ord.emplace_back(0);
        while(l < r){
            int i = ord[l]; l++;
            for (int c = 0; c < W; ++c) {
                if(!v[i].to[c]) continue;
                int to = v[i].to[c];
                v[to].fail = (v[i].fail == -1 ? 0 : v[v[i].fail].to[c]);
                ord.emplace_back(to);
                r++;
            }
            if(i != 0){
                for (int c = 0; c < W; ++c) {
                    if(!v[i].to[c]) v[i].to[c] = v[v[i].fail].to[c];
                }
            }
        }
    }
    inline int next(int x, char c){ return v[x].to[c-start]; }
};


int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(nullptr);
    AhoCorasick<26, 'A'> aho;
    string s;
    cin >> s;
    int m;
    cin >> m;
    vector<int> ids(m);
    vector<string> x(m);
    for (int i = 0; i < m; ++i) {
        string t;
        cin >> t;
        x[i] = t;
        ids[i] = aho.add(t);
    }
    aho.build();
    vector<int> dp(aho.v.size());
    for (int i = 0; i < m; ++i) {
        dp[ids[i]]++;
    }
    for (auto &&i : aho.ord) {
        if(i) dp[i] += dp[aho.v[i].fail];
    }
    int cur = 0, ans = 0;
    for (auto &&i : s) {
        cur = aho.next(cur, i);
        ans += dp[cur];
    }
    cout << ans << "\n";
    return 0;
}
0