HDU - 2222 Keywords Search AC自动机 - ProLightsfx的技术成长

Keywords Search AC自动机

Source

My Solution

题意：给出n个字符串为这些字符串在主串s中出现的个数。

AC自动机

裸的AC自动机，注意下给定模式串可能有一些相同的串，然后按照主串在自动机上遍历即可。

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int CHAR_SIZE = 26;
const int MAX_SIZE = 5e5 + 8;
map<char, int> mp;

struct AC_Machine{
    int ch[MAX_SIZE][CHAR_SIZE], danger[MAX_SIZE], fail[MAX_SIZE];
    int sz;

    inline void init(){
        sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        memset(danger, 0, sizeof danger);
    }

    inline void _insert(const string &s){
        int n = s.size();
        int u = 0, c;
        for(int i = 0; i < n; i++){
            c = mp[s[i]];
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof ch[sz]);
                danger[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        danger[u]++;
    }

    inline void _build(){
        queue Q;
        fail[0] = 0;
        for(int c = 0, u; c < CHAR_SIZE; c++){
            u = ch[0][c];
            if(u){Q.push(u); fail[u] = 0;}
        }
        int r;
        while(!Q.empty()){
            r = Q.front();
            Q.pop();
            //danger[r] |= danger[fail[r]];
            for(int c = 0, u; c < CHAR_SIZE; c++){
                u = ch[r][c];
                if(!u){ch[r][c] = ch[fail[r]][c]; continue; }
                fail[u] = ch[fail[r]][c];
                Q.push(u);
            }
        }
    }
}ac;

string s;

int main()
{
    #ifdef LOCAL
    freopen("3.in", "r", stdin);
    //freopen("3.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    int T, n, len, now, i, ans, tmp;
    for(int i = 0; i < 26; i++){mp[(i + 'a')] = i;} cin >> T;
    while(T--){
        cin >> n;
        ac.init();
        while(n--){
            cin >> s;
            ac._insert(s);
        }
        ac._build();

        cin >> s;
        ans = 0; len = s.size(); now = 0;
        for(i = 0; i < len; i++){
            now = ac.ch[now][mp[s[i]]];
            tmp = now;
            while(tmp){
                if(ac.danger[tmp]){
                    ans += ac.danger[tmp];
                    ac.danger[tmp] = 0;
                }
                tmp = ac.fail[tmp];
            }
        }
        cout << ans << "n";
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

HDU – 2222 Keywords Search AC自动机

相关推荐

HDU 6138 Fleet of the Eternal Throne 后缀数组+字典树

XIII Open Championship Problem E. Enter the Word Problem 后缀自动机+贪心

HDU 6208 The Dominator of Strings 后缀自动机

Petrozavodsk Winter-2013. Ural FU Contest Problem D. Five Palindromes manacher、一个串切割成5个回文子串、优化

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类