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

[AC自动机]zoj 3228:Searching the String

阅读更多

大致题意:

    给出n组模式串数据,每组数据由一个01数字和一个模式串组成,再给出一个文本串。对于每组模式串数据,分别统计其在文本串中出现了多少次,如果前面的数字是0,则代表计数的时候可以重叠,如果是0则代表不能重叠。

 

大致思路:
    好麻烦的一道题,有思路但是真的很难敲,要用多个数组来控制好数据之间的关系,最后还狂mle……擦。对于可以重叠的,直接ac自动机即可,对于不能重叠的,求出当前的位置距离其上次匹配的距离再判断即可。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=600002;
const int mMax=100002;
class node{
public:
    int id;
    int count,len;
    node *next[26],*fail;
    node(){
        id=-1;
        count=0;           //count用来记录当前这个节点的询问状态
        fail=NULL;
        for(int i=0;i<26;i++)next[i]=NULL;
    }
}*root,*que[nMax];
int cnt;
int insert(char *s,int d){    //构造前缀树
    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];
    }
    if(r->id==-1){
        r->id=cnt;
        cnt++;
    }
    r->len=l;
    r->count|=d;
    return r->id;
}

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 vis[nMax][2],last[nMax],type[mMax],loc[mMax];
char str[10],text[mMax];
void search(int n){
    int i,idx;
    node *p=root,*tmp;
    for(i=0;text[i];i++){
        idx=text[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=tmp->fail){//&&tmp->count!=-1   因为这里需要求的是该字符串出现的次数
            if(tmp->id!=-1){
                if(tmp->count&1){
                    vis[tmp->id][0]++;
                }
                if(tmp->count&2){
                    if(i-tmp->len+1>last[tmp->id]){
                        vis[tmp->id][1]++;
                        last[tmp->id]=i;
                    }
                }
            }
        }
    }
}

int main(){
    int n,i,j,flag,a,cas=0;
    while(scanf("%s",text)!=EOF){
        cas++;
        cnt=1;
        root=new node();
        memset(vis,0,sizeof(vis));
        memset(last,-1,sizeof(last));
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d%s",&type[i],str);
            loc[i]=insert(str,type[i]+1);
        }
        acAuto();
        search(n);
        printf("Case %d\n",cas);
        int k;
        for(i=0;i<n; i++){
            if(type[i]==0){
                k=0;
            }else{
                k=1;
            }
            k=vis[loc[i]][k];
            printf("%d\n", k);
        }
        printf("\n");
    }
    return 0;
}
 
0
0
分享到:
评论

相关推荐

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

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

    AC自动机_AC自动机模板_

    供信息学奥林匹克竞赛选手使用 AC自动机模板

    ac自动机.pptx

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

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

    基于单模式串和 Trie 树实现的敏感词过滤我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,前面四种算法都是单模式串

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

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

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

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

    AC自动机.pdf

    AC自动机算法是解决这种问题的一个经典方法,时间复杂度为O(n+m+z),其中z是T中出现的模式串的数量。AC自动机是基于keyword tree的,并对其进行一些补充。

    自己写的ac自动机,STL实现

    相当给力,头文件中附带了简单的使用方法,使用istream当接口,因此你可以传入stringstream或fstream,甚至可以自己派生istream再传入,支持全文查找和增量查找两种模式,有问题可以联系我

    AC 自动机算法

    AC自动机算法

    ACAuto自动机 多模式匹配 多字符串匹配

    AC自动机算法的实现。AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章...

    AC自动机pdf

    关于AC自动机的pdf文档,很清楚的讲解了AC自动机算法及应用

    中文高性能AC自动机代码

    C语言实现,效率极高,实现了中文的关键字匹配,输出的格式为偏移量加上关键字(中文编码为GB2312)

    AC自动机详解+例题详解

    关于AC自动机的详细的讲解+标程,还有一些例题的讲解。

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

    AC自动机实现多模式串匹配,支持中文系统,同时可以支持多个模式串,测试使用Linux和Windows系统,使用20条模式串,中英文混合,测试通过

    文学研究助手(AC自动机版本)

    文学研究助手,AC自动机版本,数据结构 利用AC自动机只对文件进行一次扫描,统计要查询的单词在文档出现的次数及所在行

    AC自动机模板

    AC自动机模板,直接套,有注释N的范围,适合初学者学习

    AC自动机

    基于字典树的ac自动机,自己前期的实现,具有源码参考,用于查找可屏蔽应用

    中文AC自动机

    中文AC自动机,可以用于中文字符串,可以结合中文分词使用

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

    AC自动机最全数据,大家可以看一下,欢迎下载,谢谢支持!!!!!!!!!!!!!!!!!!!!!!!!

    AC算法 树型自动机

    基于AC算法的多模式特征匹配算法实现, 树型自动机的预处理:转向函数、失效函数、输出函数构建

Global site tag (gtag.js) - Google Analytics