WA自动鸡
2018-06-27 10:06:03来源:未知 阅读 ()
WA鸡
不信啊,你交交试试。
Trie树+next数组。
WA模板。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<queue> #include<algorithm> using namespace std; int size,sumsize; struct AC { int son[1000001][30]; int last[1000001]; int fail[1000001]; int back[1000001]; void clear() { memset(son[0],0,sizeof(son[0])); size=1; } void clear_x(int x) { memset(son[x],0,sizeof(son[x])); back[x]=0; } void insert(char *a) { int len=strlen(a); int now=0; for(int i=0;i<len;i++) { int c=a[i]-'a'; if (!son[now][c]) { clear_x(size); son[now][c]=size++; } now=son[now][c]; } back[now]++; } void gf() { queue<int> q; int u=0; fail[0]=0; for(int i=0;i<sumsize;i++) { u=son[0][i]; if (u) { q.push(u);fail[u]=0;last[u]=0; } } while(!q.empty()) { int f=q.front(); q.pop(); for(int i=0;i<sumsize;i++) { u=son[f][i]; if (!u) { son[f][i]=son[fail[f]][i]; continue; } q.push(u); int v=fail[f]; while(v&&!son[v][i]) v=fail[v]; fail[u]=son[v][i]; last[u]=back[fail[u]]?fail[u]:last[fail[u]]; } } } int find(char *a) { int u=0,cnt=0; int len=strlen(a); for(int i=0;i<len;i++) { int c=a[i]-'a'; u=son[u][c]; int tmp=0; if (back[u])tmp=u; else if (last[u]) tmp=last[u]; while(tmp) { cnt+=back[tmp]; back[tmp]=0; tmp=last[tmp]; } } return cnt; } }WA; char s[1000001]; int n; int main() { int t;sumsize=27; scanf("%d",&t); while(t--) { WA.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",s); WA.insert(s); } WA.gf(); scanf("%s",s); printf("%d\n",WA.find(s)); return 0; } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:内存对齐
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ 自动变量 2020-05-10
- C++ 存储持续性 2020-05-10
- P3121 [USACO15FEB]审查(AC自动机) 2019-08-16
- 类型转换 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash