网站参考页面设计,wordpress loginview,界面设计效果图排版,域名服务器在哪个国家题目链接 http://acm.hdu.edu.cn/showproblem.php?pid2222 题意#xff1a;给你一系列子串#xff0c;再给你一个主串问你主串一共有几个匹配子串 原来使用字典树写的但数据有点大TLE了#xff0c;然后就开始学习ac自动机了#xff0c;ac自动机就像是多串匹配的kmp原理也是… 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid2222 题意给你一系列子串再给你一个主串问你主串一共有几个匹配子串 原来使用字典树写的但数据有点大TLE了然后就开始学习ac自动机了ac自动机就像是多串匹配的kmp原理也是类似的。 这题可以练一下手写ac自动机模版。 #include iostream
#include cstring
#include cstdio
#include queue
using namespace std;
const int M 5e5 50;
int Next[M][26] , fail[M] , End[M] , root , L , cnt;
char str[60] , sl[M * 2];
int newnode() {for(int i 0 ; i 26 ; i) {Next[L][i] -1;}End[L] 0;return L - 1;
}
void init() {L 0;root newnode();
}
void build(char s[]) {int len strlen(s);int now root;for(int i 0 ; i len ; i) {int id s[i] - a;if(Next[now][id] -1) {Next[now][id] newnode();}now Next[now][id];}End[now];
}
void get_fail() {queueintq;fail[root] root;for(int i 0 ; i 26 ; i) {if(Next[root][i] -1) {Next[root][i] root;}else {fail[Next[root][i]] root;q.push(Next[root][i]);}}while(!q.empty()) {int now q.front();q.pop();for(int i 0 ; i 26 ; i) {if(Next[now][i] -1) {Next[now][i] Next[fail[now]][i];}else {fail[Next[now][i]] Next[fail[now]][i];q.push(Next[now][i]);}}}
}
void match(char s[]) {int now root;int len strlen(s);for(int i 0 ; i len ; i) {int id s[i] - a;now Next[now][id];int temp now;while(temp ! root) {cnt End[temp];End[temp] 0;temp fail[temp];}}
}
int main()
{int t;scanf(%d , t);while(t--) {int n;scanf(%d , n);init();for(int i 0 ; i n ; i) {scanf(%s , str);build(str);}get_fail();scanf(%s , sl);cnt 0;match(sl);printf(%d\n , cnt);}return 0;
}转载于:https://www.cnblogs.com/TnT2333333/p/6080469.html
