大致题意:
给出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;
}
分享到:
相关推荐
多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 ...
供信息学奥林匹克竞赛选手使用 AC自动机模板
要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...
基于单模式串和 Trie 树实现的敏感词过滤我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,前面四种算法都是单模式串
AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
AC自动机AC自动机AC自动机AC自动机
AC自动机算法是解决这种问题的一个经典方法,时间复杂度为O(n+m+z),其中z是T中出现的模式串的数量。AC自动机是基于keyword tree的,并对其进行一些补充。
相当给力,头文件中附带了简单的使用方法,使用istream当接口,因此你可以传入stringstream或fstream,甚至可以自己派生istream再传入,支持全文查找和增量查找两种模式,有问题可以联系我
本项目是一款高效的Java敏感词过滤系统,基于AC自动机算法实现。系统支持独立部署,同时可便捷集成至注册中心,为各类项目提供敏感词过滤服务。包含文件共117个,其中主要构成如下: - Java源文件:49个 - Class...
AC自动机算法
AC自动机算法的实现。AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章...
关于AC自动机的pdf文档,很清楚的讲解了AC自动机算法及应用
C语言实现,效率极高,实现了中文的关键字匹配,输出的格式为偏移量加上关键字(中文编码为GB2312)
关于AC自动机的详细的讲解+标程,还有一些例题的讲解。
AC自动机实现多模式串匹配,支持中文系统,同时可以支持多个模式串,测试使用Linux和Windows系统,使用20条模式串,中英文混合,测试通过
文学研究助手,AC自动机版本,数据结构 利用AC自动机只对文件进行一次扫描,统计要查询的单词在文档出现的次数及所在行
Finite Automaton 有限状态自动机 Finite Automaton 有限状态自动机是计算机科学中的一种基本模型,用于描述有限状态机的行为。它是一种数学模型,用于描述一个系统在不同的状态之间转换的过程。 Finite Automaton...
AC自动机模板,直接套,有注释N的范围,适合初学者学习
基于字典树的ac自动机,自己前期的实现,具有源码参考,用于查找可屏蔽应用
中文AC自动机,可以用于中文字符串,可以结合中文分词使用