[洛谷3808]【模板】AC自动机(简单版)
2024-08-28 09:32:14
题目大意:
给定$n$个模式串$p(\sum|p_i|\le10^6)$和一个$t(|t|\le10^6)$,求在$t$中被匹配的$p$的个数。
思路:
AC自动机模板题,注意$t$中一个字符可能对应自动机上多个结点,因此需要按照失配指针跳转统计。统计过的结点需要特殊标记,避免重复统计,否则会超时。
#include<queue>
#include<cstdio>
#include<cctype>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int N=1e6+,S=;
char s[N];
int ans=;
class AhoCorasick {
private:
std::queue<int> q;
int val[N],ch[N][S],fail[N];
int sz,new_node() {
return ++sz;
}
int idx(const char &c) const {
return c-'a';
}
public:
void insert(const char s[]) {
int p=;
for(register int i=;s[i];i++) {
if(!ch[p][idx(s[i])]) ch[p][idx(s[i])]=new_node();
p=ch[p][idx(s[i])];
}
val[p]++;
}
void get_fail() {
for(register int i=;i<S;i++) {
if(ch[][i]) q.push(ch[][i]);
}
while(!q.empty()) {
const int &x=q.front();
for(register int i=;i<S;i++) {
if(!ch[x][i]) {
ch[x][i]=ch[fail[x]][i];
continue;
}
fail[ch[x][i]]=ch[fail[x]][i];
q.push(ch[x][i]);
}
q.pop();
}
}
void find(const char s[]) {
int p=;
for(register int i=;s[i];i++) {
p=ch[p][idx(s[i])];
for(register int q=p;q&&~val[q];q=fail[q]) {
ans+=val[q];
val[q]=-;
}
}
}
};
AhoCorasick ac;
int main() {
const int n=getint();
for(register int i=;i<n;i++) {
scanf("%s",s);
ac.insert(s);
}
ac.get_fail();
scanf("%s",s);
ac.find(s);
printf("%d\n",ans);
return ;
}
最新文章
- Linux搜索文件夹下所有文件中字符串
- c++中this指针的用法
- HDU 4419 Colourful Rectangle --离散化+线段树扫描线
- Java Web文件上传
- 黄聪:jquery mobile通过a标签页面跳转后,样式丢失、js失效的解决方法
- 【BZOJ 2120】 数颜色
- To follow the path
- Leetcode#143 Reorder List
- python-os.walk目录递归
- 第八十二节,CSS3过渡效果
- HSRP(Hot Standby Router Protocol)
- 数据库事务的四大特性以及事务的隔离级别(mysql)
- Java几种常用JSON库性能比较
- 导出使用NPOI
- NodeJs第3方包说明
- eclipse 设置Java快捷键补全
- L1-022 奇偶分家
- ubuntu14.04上编译安装python3.7.3
- 黑盒测试实践--Day1 11.25
- Python 自用代码(递归清洗采标情况)