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);
    }
}

相关文章
|
12月前
|
C++
AC自动机
AC自动机
57 0
|
3月前
|
算法 Python
Aho-Corasick 算法 AC自动机实现
Aho-Corasick 算法 AC自动机实现
62 0
|
3月前
|
存储 算法
HanLP — Aho-Corasick DoubleArrayTire 算法 ACDAT - 基于双数组字典树的AC自动机
HanLP — Aho-Corasick DoubleArrayTire 算法 ACDAT - 基于双数组字典树的AC自动机
44 0
|
4月前
|
算法
后缀数组算法介绍
后缀数组学习
38 2
|
5月前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
25 0
|
5月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
存储 Java
Java数据结构之第十五章、Trie(前缀树/单词查找树)
1.前缀树的概念:前缀树又叫字典树或单词查找树(高效的存储和查找字符串集合的数据结构)。2.3.存储形式:存储的字符串可能:全是 小写字母 或全是 大写字母 或全是 数字 或全是 0和1。它是一棵,每个代表一个,从。字典树的根节点不包含字符,每个子节点代表一个字符,从根节点到任意一个节点所经过的路径上的字符连接起来即为该节点所代表的字符串。每个节点可以存储一个或多个字符串,通常使用一个标志来标记一个节点代表的字符串是否存在。当需要在一组字符串中查找某个字符串时,可以利用字典树来实现高效的查找操作。
73 0
|
算法 测试技术 Android开发
LeetCode 周赛上分之旅 # 36 KMP 字符串匹配殊途同归
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
76 0
|
存储 算法 BI
KMP算法(kmp) next数组算法解析
KMP算法(kmp) next数组算法解析
141 0
KMP算法(kmp) next数组算法解析