洛谷P3796 【模板】AC自动机(加强版)
2018-07-03 01:01:18来源:博客园 阅读 ()
题目描述
有 NN 个由小写字母组成的模式串以及一个文本串 TT 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 TT 中出现的次数最多。
输入输出格式
输入格式:
输入含多组数据。
每组数据的第一行为一个正整数 NN ,表示共有 NN 个模式串, 1 \leq N \leq 1501≤N≤150 。
接下去 NN 行,每行一个长度小于等于 7070 的模式串。下一行是一个长度小于等于 10^6106 的文本串 TT 。
输入结束标志为 N=0N=0 。
输出格式:
对于每组数据,第一行输出模式串最多出现的次数,接下去若干行每行输出一个出现次数最多的模式串,按输入顺序排列。
输入输出样例
2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0
4 aba 2 alpha haha
这题真是迷啊,开1e6的内存A了,开1e5的内存MLE
我们统计出每个节点的出现信息,然后暴力沿着$fail$树跑就行了
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; const int MAXN = 1e6 + 10, B = 26; int T; char s[201][75], a[MAXN]; int N; int fail[MAXN], ch[MAXN][27], val[MAXN], root = 0, tot = 0, sum[MAXN]; void insert(char *s, int I) { int N = strlen(s + 1); int now = root; for(int i = 1; i <= N; i++) { int x = s[i] - 'a'; if(!ch[now][x]) ch[now][x] = ++tot; now = ch[now][x]; } val[now] = I; } void GetFail() { queue<int> q; for(int i = 0; i < B; i++) if(ch[root][i]) q.push(ch[root][i]); while(!q.empty()) { int p = q.front(); q.pop(); for(int i = 0; i < B; i++) if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]); else ch[p][i] = ch[fail[p]][i]; } } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif while(scanf("%d", &T) && T) { memset(fail, 0, sizeof(fail)); memset(ch, 0, sizeof(ch)); memset(val, 0, sizeof(val)); memset(fail, 0, sizeof(fail)); memset(sum, 0, sizeof(sum)); memset(s, 0, sizeof(s)); for(int i = 1; i <= T; i++) scanf("%s", s[i] + 1), insert(s[i], i); GetFail(); scanf("%s", a + 1); int N = strlen(a + 1), now = root; for(int i = 1; i <= N; i++) { now = ch[now][a[i] - 'a']; for(int t = now; t; t = fail[t]) if(val[t]) sum[val[t]]++; } int ans = 0; for(int i = 1; i <= T; i++) ans = max(ans, sum[i]); printf("%d\n", ans); for(int i = 1; i <= T; i++) if(sum[i] == ans) printf("%s\n", s[i] + 1); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
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