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);
    }
}
AI 代码解读

目录
打赏
0
0
0
0
1
分享
相关文章
Unity Shader Graph 制作Rim Light边缘光效果
Unity Shader Graph 制作Rim Light边缘光效果
639 0
Unity Shader Graph 制作Rim Light边缘光效果
技术:Java-Web基础|生成图片验证码(二)
验证码(CAPTCHA)是“Completely Automated Public Turing test to tell Computers and Humans Apart”(全自动区分计算机和人类的图灵测试)的缩写,是一种区分用户是计算机还是人的公共全自动程序。可以防止:恶意破解密码、刷票、论坛灌水,有效防止某个黑客对某一个特定注册用户用特定程序暴力破解方式进行不断的登陆尝试,实际上用验证码是现在很多网站通行的方式,我们利用比较简易的方式实现了这个功能。这个问题可以由计算机生成并评判,但是必须只有人类才能解答。由于计算机无法解答CAPTCHA的问题,所以回答出问题的用户就可以被认为是人类
技术:Java-Web基础|生成图片验证码(二)
飞天加速计划·高校学生在家畅快趣学
领取性能强劲的阿里云ECS,添加公钥,创建sudoer后,借助快如闪电⚡的阿里云镜像源与容器镜像加速服务,使用docker工具畅快学习使用 Nginx、Consul、Postgres、RabbitMQ等强大应用👍
JS 如何判断是否安装某个 Android APP?
在实际工作场景中,我们经常会遇到这种需求:需要提示用户下载 App,而如果用户已经安装,我们希望是直接打开 App。
1611 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问