結果

問題 No.430 文字列検索
ユーザー mamekin
提出日時 2016-10-05 12:42:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 2,909 bytes
コンパイル時間 1,279 ms
コンパイル使用メモリ 118,968 KB
実行使用メモリ 15,912 KB
最終ジャッジ日時 2024-11-10 00:09:24
合計ジャッジ時間 1,918 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

class AhoCorasick
{
private:
    int n;
    vector<vector<int> > next;
    vector<vector<int> > match;
    vector<int> failure;
public:
    AhoCorasick(const vector<string>& pattern){
        next.assign(1, vector<int>(128, -1));
        match.assign(1, vector<int>());
        for(unsigned i=0; i<pattern.size(); ++i){
            int curr = 0;
            for(unsigned j=0; j<pattern[i].size(); ++j){
                if(next[curr][pattern[i][j]] == -1){
                    next[curr][pattern[i][j]] = next.size();
                    next.push_back(vector<int>(128, -1));
                    match.push_back(vector<int>());
                }
                curr = next[curr][pattern[i][j]];
            }
            match[curr].push_back(i);
        }

        n = next.size();
        failure.resize(n, 0);
        vector<int> node1(1, 0);
        while(!node1.empty()){
            vector<int> node2;
            for(unsigned i=0; i<node1.size(); ++i){
                for(int j=0; j<128; ++j){
                    int s = node1[i];
                    if(next[s][j] == -1)
                        continue;
                    node2.push_back(next[s][j]);
                    int t = s;
                    while(t != 0){
                        if(next[failure[t]][j] != -1){
                            failure[next[s][j]] = next[failure[t]][j];
                            copy(match[next[failure[t]][j]].begin(), match[next[failure[t]][j]].end(), std::back_inserter( match[next[s][j]]));
                            break;
                        }
                        t = failure[t];
                    }
                }
            }
            node1.swap(node2);
        }

        for(int i=0; i<n; ++i)
            sort(match[i].begin(), match[i].end());
    }
    int size(){
        return n;
    }
    int transit(int curr, char c){
        if(next[curr][c] != -1)
            return next[curr][c];
        if(curr == 0)
            return 0;
        return transit(failure[curr], c);
    }
    const vector<int>& checkMatch(int curr){
        return match[curr];
    }
};

int main()
{
    string s;
    int m;
    cin >> s >> m;
    int n = s.size();

    vector<string> c(m);
    for(int i=0; i<m; ++i)
        cin >> c[i];

    AhoCorasick ac(c);
    int k = 0;
    int ans = 0;
    for(int i=0; i<n; ++i){
        k = ac.transit(k, s[i]);
        ans += ac.checkMatch(k).size();
    }
    cout << ans << endl;

    return 0;
}
0