AC自动机

简介: #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<queue> using namespace std; int T[400100][26] =.


28ec279e10e2350996df47ddd17a294af083c6cf

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int T[400100][26] = {0};
int last[401000], f[410000], val[410000];
int sz = 0;
void     _Insert(string s){
    int u = 0;
    for (int i = 0; s[i]; i++){
        int c = s[i] - 'a';
        if (!T[u][c]){
            T[u][c] = ++sz;
            val[sz] = 0;            
        }
        u = T[u][c];
    }
    val[u] ++;
}
char s[1000100];
void build(){
    queue<int> q;
    for (int i = 0; i < 26; i++){
        int u = T[0][i];
        if (u){
            f[u] = last[u] = 0;
            q.push(u);
        }
    }
    while (!q.empty()){
        int h = q.front(); q.pop();
        for (int i = 0; i < 26; i++){
            int u = T[h][i], v = f[h];
            if (!u){
                T[h][i] = T[v][i];
                continue;
            }
            q.push(u);
            while (v && !T[v][i]) v = f[v];
            f[u] = T[v][i];
            last[u] = val[f[u]] ? f[u] : last[f[u]];
        }
    }
}

long long sum = 0;
void print(int j){
    if (j){
        sum += val[j];
        val[j] = 0;
        print(last[j]);
    }
}
void aFind(){
    int j = 0;
    for (int i = 0; s[i]; i++){
        int c = s[i] - 'a';
        j = T[j][c];
        if (val[j]) print(j);
        else if (last[j]) print(last[j]);    
    }
}

int main(){
    int t;
    cin>>t;
    while (t--){
        int n; cin>>n;
        memset(T, 0, sizeof(T));sz = 0;
        memset(last, 0 ,sizeof(last));
        memset(f, 0, sizeof (f));
        memset(val, 0, sizeof(val));
        for (int i = 0; i < n; i++){
            string a;
            cin>>a;
            _Insert(a);
        }
        build();
        scanf("%s", s);
        sum = 0;
        aFind();
        printf("%d\n", sum);
    }
}

相关文章
AC自动机
AC自动机
59 0
|
3月前
|
算法 Python
Aho-Corasick 算法 AC自动机实现
Aho-Corasick 算法 AC自动机实现
72 0
|
3月前
|
存储 算法
HanLP — Aho-Corasick DoubleArrayTire 算法 ACDAT - 基于双数组字典树的AC自动机
HanLP — Aho-Corasick DoubleArrayTire 算法 ACDAT - 基于双数组字典树的AC自动机
50 0
|
4月前
|
算法
后缀数组算法介绍
后缀数组学习
41 2
|
5月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
6月前
|
算法 测试技术 C++
【动态规划】 【字典树】C++算法:472 连接词
【动态规划】 【字典树】C++算法:472 连接词
|
存储 Java
Java数据结构之第十五章、Trie(前缀树/单词查找树)
1.前缀树的概念:前缀树又叫字典树或单词查找树(高效的存储和查找字符串集合的数据结构)。2.3.存储形式:存储的字符串可能:全是 小写字母 或全是 大写字母 或全是 数字 或全是 0和1。它是一棵,每个代表一个,从。字典树的根节点不包含字符,每个子节点代表一个字符,从根节点到任意一个节点所经过的路径上的字符连接起来即为该节点所代表的字符串。每个节点可以存储一个或多个字符串,通常使用一个标志来标记一个节点代表的字符串是否存在。当需要在一组字符串中查找某个字符串时,可以利用字典树来实现高效的查找操作。
77 0
|
存储 算法 Linux
秒懂算法 | 字典树
字典树是一种基础方法,请掌握字典树的静态数组存储方法,它在后缀树、回文树、AC自动机、后缀自动机中都要用到。
156 0
|
存储 算法 BI
KMP算法(kmp) next数组算法解析
KMP算法(kmp) next数组算法解析
145 0
KMP算法(kmp) next数组算法解析