大致题意:
给出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自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于信息学奥林匹克竞赛、数据结构与算法竞赛以及文本处理等领域。它的主要功能是高效地在一个字符串集合中进行多模式匹配,即同时查找多个模式串...
AC自动机是一种高效的多模式串匹配算法,主要应用于文本处理中的敏感词过滤、关键词搜索等功能。它的全称为Aho-Corasick算法,由Aho和Corasick在1975年提出。AC自动机在Trie树的基础上进行了扩展,增加了失败指针,...
**支持多线程AC自动机** 在网络安全领域,Snort是一款广泛应用的开源网络入侵检测系统(IDS)。它能够实时分析网络流量,识别潜在的攻击行为。然而,原版的Snort可能在处理大量数据时面临性能瓶颈,因为它通常是单...
AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于文本处理、生物信息学、搜索引擎等领域。这个压缩包包含了多个以".in"为后缀的文件,很可能是用于AC自动机相关的编程练习或测试数据集。 AC...
**AC自动机(Aho-Corasick算法)**是一种在字符串搜索中用于高效查找多个模式串的算法。在中文文本处理中,AC自动机尤其适用,因为它能够一次性处理大量关键词,避免了对文本的多次扫描。这个算法由Aho和Corasick在...
### 多模式匹配:AC自动机与DAWG自动机 #### 概述 多模式匹配是一种在文本中查找多个模式(关键词或字符串)的技术,在数据挖掘、信息安全、生物信息学等多个领域有着广泛的应用。例如,在数据挖掘中可以用于发现...
要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...
### AC自动机详解 #### 一、AC自动机概述 AC自动机(Aho-Corasick Automaton)是一种经典的字符串匹配算法,特别适用于处理多个模式串的匹配问题。它结合了KMP算法的思想以及字典树(Trie)的结构特点,能够有效地在...
AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
**AC自动机(Aho-Corasick算法)**是一种高效的字符串搜索算法,它基于字典树(Trie)数据结构,能够一次性查找多个模式串在文本中的出现情况。AC自动机的主要优势在于避免了对同一个文本位置多次进行模式匹配,大大...
AC自动机AC自动机AC自动机AC自动机
**AC自动机(Aho-Corasick Algorithm)模板** AC自动机是一种字符串搜索算法,它在文本中查找多个模式串的出现情况。该算法由艾伦·科拉斯和戈登·科拉斯在1975年提出,是KMP算法和后缀自动机的结合,具有高效性和...
AC自动机,全称为Aho-Corasick自动机,是一种在文本中高效地进行多模式串匹配的算法。它的核心思想是构建一个自动机结构,该结构能够在一次遍历文本的过程中,同时匹配多个模式串,大大提高了搜索效率,避免了对每一...
- **高效性**:AC自动机可以在O(n+m)的时间复杂度内完成多模式匹配,其中n是文本的长度,m是所有模式串的总长度。 - **预处理**:通过构建AC自动机,可以将模式串的信息进行预处理,从而加速后续的匹配过程。 - **...
AC自动机(Aho-Corasick自动机)是一种高效的算法,用于解决多模式字符串匹配问题。它结合了字典树(Trie树)的数据结构,能够一次性查找多个模式串在文本中的出现情况。接下来,我们将深入探讨AC自动机的工作原理、...
AC自动机,全称为Aho-Corasick算法,是一种在字符串搜索中用于高效查找多个模式的算法。在Java编程环境中,AC自动机被广泛应用于文本处理、数据分析、搜索引擎等领域,尤其是处理大规模数据时,它的效率尤为突出。这...
AC自动机,全称为Aho-Corasick自动机,是一种字符串搜索算法,广泛应用于文本处理、数据挖掘等领域。它在ACM(国际大学生程序设计竞赛)中也是一项重要的算法技能,因为它能高效地解决字符串匹配问题,特别是面对...
- 时间复杂度:AC自动机可以在O(n + m)的时间内完成n个模式在m长度的文本中的查找,其中n是模式串的数量,m是文本的长度。这比朴素的逐个模式匹配方法效率高得多。 - 并行性:AC自动机可以同时检查多个模式,适合...
### AC自动机详解及其在生物序列算法中的应用 #### 一、引言 AC自动机,也称为Aho-Corasick算法,是一种经典的字符串搜索算法,由Alfred V. Aho与Margaret J. Corasick于1975年提出。该算法主要用于在一个文本串中...