题目大意:
  给定$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 ;
}

最新文章

  1. Linux搜索文件夹下所有文件中字符串
  2. c++中this指针的用法
  3. HDU 4419 Colourful Rectangle --离散化+线段树扫描线
  4. Java Web文件上传
  5. 黄聪:jquery mobile通过a标签页面跳转后,样式丢失、js失效的解决方法
  6. 【BZOJ 2120】 数颜色
  7. To follow the path
  8. Leetcode#143 Reorder List
  9. python-os.walk目录递归
  10. 第八十二节,CSS3过渡效果
  11. HSRP(Hot Standby Router Protocol)
  12. 数据库事务的四大特性以及事务的隔离级别(mysql)
  13. Java几种常用JSON库性能比较
  14. 导出使用NPOI
  15. NodeJs第3方包说明
  16. eclipse 设置Java快捷键补全
  17. L1-022 奇偶分家
  18. ubuntu14.04上编译安装python3.7.3
  19. 黑盒测试实践--Day1 11.25
  20. Python 自用代码(递归清洗采标情况)

热门文章

  1. glance上传镜像
  2. 洛谷P1071潜伏者(提高组)
  3. 团队项目-第七次scrum 会议
  4. 二分查找树按照key值划分
  5. 【转】IDEA 2017破解 license server激活
  6. code forces 994C
  7. NetAPP常用操作
  8. Mysql 索引原理(转自:张洋)
  9. 乌班图 root权限获取
  10. 用VS2010编写的C++程序,在其他电脑上无法运行的问题