#796565 (C++17) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: pockyny
• 提出日時: 2022-09-11 00:04:47
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 38 ms / 2,000 ms
• コード長: 6,192 bytes
• コンパイル時間: 1,528 ms
• コンパイル使用メモリ: 97,168 KB
• 最終ジャッジ日時: 2025-02-07 04:11:55
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 14

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <array>
#include <queue>

using namespace std;
const int alpha = 26;//alphabet_size
struct AhoCorasick{
    int sumLength = 0;//sum of |P_i| + 1
    vector<string> pattern;
    vector<array<int,alpha>> Trie;
    vector<int> failureLink;
    vector<int> isEnd;
    vector<int> trulyFailureLink,dist; // it is not used for counting but used for enumerating
    vector<vector<int>> failureTree; // it is not used for enumerating but used for counting
    AhoCorasick(vector<string> &P){
        createTrie(P);
        createFailureLink();
        createTrulyFailureLink();
        createFailureTree();
    }
    //make Trie
    void createTrie(vector<string> &P){
        pattern = P;
        sumLength = 1;
        for(string str:pattern) sumLength += str.size();
        Trie.resize(sumLength + 1);
        isEnd.resize(sumLength + 1);
        int index = 1;
        int maxPosition = 1;
        for(string str:pattern){
            int position = 1; //the index of root = 1;
            int latestEnd = 1;
            for(char chr:str){
                if(!Trie[position][chr - 'A']) Trie[position][chr - 'A'] = ++maxPosition;
                position = Trie[position][chr - 'A'];
            }
            isEnd[position] = index++;
        }
    }
    //make failureLink
    void createFailureLink(){
        failureLink.resize(sumLength + 1);
        dist.resize(sumLength + 1);
        failureLink[1] = 1;
        queue<pair<int,int>> bfsQue;
        bfsQue.push({1,0});
        while(bfsQue.size()){
            int position = bfsQue.front().first;
            dist[position] = bfsQue.front().second;
            bfsQue.pop();
            for(int i=0;i<alpha;i++){
                if(Trie[position][i]){
                    int nextPosition = Trie[position][i];
                    bfsQue.push({nextPosition,dist[position] + 1});
                    int tmp = position;
                    while(tmp!=1 && !Trie[failureLink[tmp]][i]){
                        tmp = failureLink[tmp];
                    }
                    if(Trie[failureLink[tmp]][i] && nextPosition!=Trie[failureLink[tmp]][i]){
                        failureLink[nextPosition] = Trie[failureLink[tmp]][i];
                    }else{
                        failureLink[nextPosition] = 1;
                    }
                }
            }
        }
    }
    // make trulyFailureLink
    void createTrulyFailureLink(){
        trulyFailureLink.resize(sumLength + 1);
        queue<int> bfsQue;
        bfsQue.push(1);
        while(bfsQue.size()){
            int position = bfsQue.front(); bfsQue.pop();
            if(position!=1){
                if(isEnd[failureLink[position]]) trulyFailureLink[position] = failureLink[position];
                else trulyFailureLink[position] = trulyFailureLink[failureLink[position]];
            }else{
                trulyFailureLink[position] = 1;
            }
            for(int i=0;i<alpha;i++){
                if(Trie[position][i]){
                    bfsQue.push(Trie[position][i]);
                }
            }
        }
    }
    // make failureTree
    void createFailureTree(){
        failureTree.resize(sumLength + 1);
        for(int i=2;i<=sumLength;i++){
            failureTree[failureLink[i]].push_back(i);
        }
    }
    // sでpatternが存在する位置を列挙する
    vector<vector<int>> enumerate(string S){
        S.push_back('z' + 1);
        vector<vector<int>> enume(pattern.size());
        int position = 1;
        int left = 0;
        for(char chr:S){
            while(position!=1 && !(chr - 'A'<alpha && Trie[position][chr - 'A'])){
                left += dist[position] - dist[failureLink[position]];
                position = failureLink[position];
            }
            if(chr - 'A'<alpha && Trie[position][chr - 'A']) position = Trie[position][chr - 'A'];
            else left++;
            int tmp = position;
            int tmpLeft = left;
            while(tmp!=1){
                if(isEnd[tmp]) enume[isEnd[tmp] - 1].push_back(tmpLeft);
                tmpLeft += dist[tmp] - dist[trulyFailureLink[tmp]];
                tmp = trulyFailureLink[tmp];
            }
        }
        return enume;
    }
    //count用のdfs関数
    vector<int> cnt;
    void dfs_cnt(int pos){
        if(pos==0) exit(1);
        for(int nextPos:failureTree[pos]){
            dfs_cnt(nextPos);
            cnt[pos] += cnt[nextPos];
        }
    }
    // sにいくつpatternが存在するか数える
    vector<int> countPattern(string S){
        cnt.resize(sumLength + 1);
        S.push_back('z' + 1); //記事中の7の代用
        int position = 1;
        for(char chr:S){
            while(position!=1 && !(chr - 'A'<alpha && Trie[position][chr - 'A'])){
                position = failureLink[position];
            }
            if(chr - 'A'<alpha && Trie[position][chr - 'A']) position = Trie[position][chr - 'A'];
            if(position!=1) cnt[position]++;
        }
        dfs_cnt(1);
        vector<int> resultOfCount(pattern.size());
        for(int i=1;i<=sumLength;i++){
            if(isEnd[i]){
                resultOfCount[isEnd[i] - 1] = cnt[i];// 1引くことに注意
            }
        }
        return resultOfCount;
    }
    void debugAhoCora(){
        for(int i=0;i<Trie.size();i++){
            cout << "i = " << i << ": ";
            for(int j=0;j<alpha;j++){
                if(Trie[i][j]) cout << "{" << char('a' + j) << ":" << Trie[i][j] << "} "; 
            }
            cout << "failure = " << failureLink[i] << endl;
        }
        cout << "isEnd = ";
        for(int i=0;i<Trie.size();i++) cout << isEnd[i] << " ";
        cout << endl;
        cout << "trulyFailureLink = ";
        for(int i=0;i<Trie.size();i++) cout << trulyFailureLink[i] << " ";
        cout << endl;
    }
};

int main(){
    string s; cin >> s;
    int i,m; cin >> m;
    vector<string> t(m);
    for(i=0;i<m;i++) cin >> t[i];
    AhoCorasick aho(t);
    int ans = 0;
    vector<vector<int>> enu = aho.enumerate(s);
    vector<int> cnt = aho.countPattern(s);
    for(i=0;i<m;i++) ans += cnt[i];
    cout << ans << endl;
}