HDU - 5384 Danganronpa AC自动机、简单题 - ProLightsfx的技术成长

Danganronpa AC自动机、简单题

Source

My Solution

题意：给出n个主串、m个模式串，求每个主串Ai中这m个模式串出现的次数和。

AC自动机、简单题

把n个模版串丢到一个队列里，然后读取m个模式串建立AC自动机，然后每个主串，按主串在AC自动机上遍历即可。注意此时的危险节点只能是模式串的结尾。

复杂度 O(n*length)

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


using namespace std;
typedef long long LL;
const int CHAR_SIZE = 26;
const int MAX_SIZE = 1e5 + 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 = s[i] - 'a';
            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;
queue sq;

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

        ac.init();
        while(m--){
            cin >> s;
            ac._insert(s);
        }
        ac._build();

        while(!sq.empty()){
            ans = 0; len = sq.front().size(); now = 0;
            for(i = 0; i < len; i++){
                now = ac.ch[now][sq.front()[i] - 'a'];
                tmp = now;
                while(tmp){
                    if(ac.danger[tmp]){
                        ans += ac.danger[tmp];
                        //ac.danger[tmp] = 0;
                    }
                    tmp = ac.fail[tmp];
                }
            }
            cout << ans << "n";
            sq.pop();
        }

    }
    return 0;
}

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

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

HDU – 5384 Danganronpa AC自动机、简单题

Danganronpa AC自动机、简单题

相关推荐

POJ – 3882 Stammering Aliens 后缀数组、二分、二叉堆、ST表

2016 UESTC Training for Search Algorithm & String K – 卿大爷的三个女友 KMP、跳转数组

UESTC 1384 卿大爷的多个女友后缀数组、最长连续重复子串

HDU – 2222 Keywords Search AC自动机

共有 0 条评论

公告

游戏服务器开发 最新文章

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

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

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

公众号

推荐系统开发 最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类

HDU – 5384 Danganronpa AC自动机、简单题

Danganronpa AC自动机、简单题

相关推荐

POJ – 3882 Stammering Aliens 后缀数组、二分、二叉堆、ST表

2016 UESTC Training for Search Algorithm & String K – 卿大爷的三个女友 KMP、跳转数组

UESTC 1384 卿大爷的多个女友 后缀数组、最长连续重复子串

HDU – 2222 Keywords Search AC自动机

共有 0 条评论

公告

游戏服务器开发最新文章

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

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

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

公众号

推荐系统开发最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类

UESTC 1384 卿大爷的多个女友后缀数组、最长连续重复子串