`
暴风雪
  • 浏览: 388998 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[AC自动机]hdoj 3695:Computer Virus on Planet Pandora

阅读更多

大致题意:
    给出n个模式串,一个文本串,求出正序和逆序文本串中一共出现了多少种模式串。文本串的输入方式很奇怪,连续的相同字母可以用[nS]代替,代表着连着共n个S。

 

大致思路:

    很奇葩的输入,处理起来有点麻烦,处理完之后就是套自动机模版了。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1003;
const int mMax=6000000;
int len2;
char str1[mMax],str2[mMax],str3[mMax];
void change(){
    int len1=strlen(str1),num,i,j;
    len2=0;
    for(i=0;i<len1;i++){
        if(str1[i]>='A'&&str1[i]<='Z'){
            str2[len2++]=str1[i];
            continue;
        }
        if(str1[i]=='['){
            i++;
            num=0;
            for(;str1[i]>='0'&&str1[i]<='9';i++){
                num=num*10+str1[i]-'0';
            }
            int ll=len2;
            for(j=ll;j<ll+num;j++){
                str2[j]=str1[i];
                len2++;
            }
            i+=1;
        }
    }
    str2[len2]='\0';
    for(i=0;i<len2;i++){
        str3[i]=str2[len2-i-1];
    }
    str3[len2]='\0';
}

class node{
public:
    int id;
    int vis;  //前缀记录标志
    node *next[26],*fail;
    node(){
        vis=0;
        fail=NULL;
        for(int i=0;i<26;i++)next[i]=NULL;
    }
}*root,*que[mMax];

void insert(char *s){    //构造前缀树
    int i;
    node *r=root;
    int l=strlen(s);
    for(i=0;i<l;i++){
        int loc=s[i]-'A';
        if(r->next[loc]==NULL){
            r->next[loc]=new node();
        }
        r=r->next[loc];
    }
    r->vis++;
}

void acAuto(){      //用bfs为每个节点设定fail指针
    int i,head=0,tail=0;
    node *p,*tmp;
    root->fail=NULL;
    que[tail++]=root;
    while(head<tail){
        tmp=que[head++];
        for(i=0;i<26;i++){
            if(tmp->next[i]==NULL)continue;
            if(tmp==root){
                tmp->next[i]->fail=root;
            }
            else {
                for(p=tmp->fail;p!=NULL;p=p->fail){
                    if(p->next[i]!=NULL){
                        tmp->next[i]->fail=p->next[i];
                        break;
                    }
                }
                if(p==NULL){
                    tmp->next[i]->fail=root;
                }
            }
            que[tail++]=tmp->next[i];
        }
    }
}

int search(char *msg){
    int i,idx,ans=0;
    node *p=root,*tmp;
    for(i=0;msg[i];i++){
        idx=msg[i]-'A';
        while(p->next[idx]==NULL&&p!=root){
            p=p->fail;
        }
        p=p->next[idx];
        if(p==NULL)p=root;
        for(tmp=p;tmp!=NULL&&tmp->vis!=-1;tmp=tmp->fail){
            ans+=tmp->vis;
            tmp->vis=-1;
        }
    }
    return ans;
}
int main(){
    int cas,n,i,ans;
    char str[nMax];
    scanf("%d",&cas);
    while(cas--){
        ans=0;
        scanf("%d",&n);
        root=new node();
        while(n--){
            scanf("%s",str);
            insert(str);
        }
        acAuto();
        scanf("%s",str1);
        change();
        ans+=search(str2);
        ans+=search(str3);
        printf("%d\n",ans);
    }
    return 0;
}
 
0
0
分享到:
评论

相关推荐

    AC自动机_AC自动机模板_

    AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于信息学奥林匹克竞赛、数据结构与算法竞赛以及文本处理等领域。它的主要功能是高效地在一个字符串集合中进行多模式匹配,即同时查找多个模式串...

    36丨AC自动机:如何用多模式串匹配实现敏感词过滤功能?1

    AC自动机是一种高效的多模式串匹配算法,主要应用于文本处理中的敏感词过滤、关键词搜索等功能。它的全称为Aho-Corasick算法,由Aho和Corasick在1975年提出。AC自动机在Trie树的基础上进行了扩展,增加了失败指针,...

    支持多线程AC自动机

    **支持多线程AC自动机** 在网络安全领域,Snort是一款广泛应用的开源网络入侵检测系统(IDS)。它能够实时分析网络流量,识别潜在的攻击行为。然而,原版的Snort可能在处理大量数据时面临性能瓶颈,因为它通常是单...

    AC自动机最全数据,欢迎下载

    AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于文本处理、生物信息学、搜索引擎等领域。这个压缩包包含了多个以".in"为后缀的文件,很可能是用于AC自动机相关的编程练习或测试数据集。 AC...

    中文高性能AC自动机代码

    **AC自动机(Aho-Corasick算法)**是一种在字符串搜索中用于高效查找多个模式串的算法。在中文文本处理中,AC自动机尤其适用,因为它能够一次性处理大量关键词,避免了对文本的多次扫描。这个算法由Aho和Corasick在...

    多模式匹配 ac自动机 dawg自动机

    ### 多模式匹配:AC自动机与DAWG自动机 #### 概述 多模式匹配是一种在文本中查找多个模式(关键词或字符串)的技术,在数据挖掘、信息安全、生物信息学等多个领域有着广泛的应用。例如,在数据挖掘中可以用于发现...

    ac自动机.pptx

    要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...

    AC自动机.pdf

    ### AC自动机详解 #### 一、AC自动机概述 AC自动机(Aho-Corasick Automaton)是一种经典的字符串匹配算法,特别适用于处理多个模式串的匹配问题。它结合了KMP算法的思想以及字典树(Trie)的结构特点,能够有效地在...

    AC自动机算法(Aho-Corasick 多模式匹配算法)

    AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现

    AC自动机

    **AC自动机(Aho-Corasick算法)**是一种高效的字符串搜索算法,它基于字典树(Trie)数据结构,能够一次性查找多个模式串在文本中的出现情况。AC自动机的主要优势在于避免了对同一个文本位置多次进行模式匹配,大大...

    AC自动机AC自动机。。。。

    AC自动机AC自动机AC自动机AC自动机

    AC自动机模板

    **AC自动机(Aho-Corasick Algorithm)模板** AC自动机是一种字符串搜索算法,它在文本中查找多个模式串的出现情况。该算法由艾伦·科拉斯和戈登·科拉斯在1975年提出,是KMP算法和后缀自动机的结合,具有高效性和...

    AC自动机实现多模式串匹配,支持中文

    AC自动机,全称为Aho-Corasick自动机,是一种在文本中高效地进行多模式串匹配的算法。它的核心思想是构建一个自动机结构,该结构能够在一次遍历文本的过程中,同时匹配多个模式串,大大提高了搜索效率,避免了对每一...

    AC自动机详解+例题详解

    - **高效性**:AC自动机可以在O(n+m)的时间复杂度内完成多模式匹配,其中n是文本的长度,m是所有模式串的总长度。 - **预处理**:通过构建AC自动机,可以将模式串的信息进行预处理,从而加速后续的匹配过程。 - **...

    字典树实现AC自动机

    AC自动机(Aho-Corasick自动机)是一种高效的算法,用于解决多模式字符串匹配问题。它结合了字典树(Trie树)的数据结构,能够一次性查找多个模式串在文本中的出现情况。接下来,我们将深入探讨AC自动机的工作原理、...

    ac自动机java版

    AC自动机,全称为Aho-Corasick算法,是一种在字符串搜索中用于高效查找多个模式的算法。在Java编程环境中,AC自动机被广泛应用于文本处理、数据分析、搜索引擎等领域,尤其是处理大规模数据时,它的效率尤为突出。这...

    AC自动机 C语言 ACM 字符串匹配|AC自动机C语言.rar

    AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于文本处理、数据挖掘等领域。它在ACM(国际大学生程序设计竞赛)中也是一项重要的算法技能,因为它能高效地解决字符串匹配问题,特别是面对...

    AC自动机程序资料合集

    - 时间复杂度:AC自动机可以在O(n + m)的时间内完成n个模式在m长度的文本中的查找,其中n是模式串的数量,m是文本的长度。这比朴素的逐个模式匹配方法效率高得多。 - 并行性:AC自动机可以同时检查多个模式,适合...

    AC自动机pdf

    ### AC自动机详解及其在生物序列算法中的应用 #### 一、引言 AC自动机,也称为Aho-Corasick算法,是一种经典的字符串搜索算法,由Alfred V. Aho与Margaret J. Corasick于1975年提出。该算法主要用于在一个文本串中...

Global site tag (gtag.js) - Google Analytics