首页 > 代码库 > UVALive 4670 Dominating Patterns
UVALive 4670 Dominating Patterns
题目链接:https://vjudge.net/problem/UVALive-4670
题意:
给一堆字符串和一个文本串,问哪些模式串在文本串中出现的次数最多,输出这个这个次数并输出这些串。
题解:
这道题是白书上的经典(模板水)题,直接上AC自动机的板子,然后xjb搞下,题目中的数据中貌似不存在相同模式串的,所以不用考虑相同串需要输出的次数(拿自己的代码和别人的对拍了一下)。
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 100; const int maxm = 5e5 + 100; struct Aho { struct state { int next[26]; int fail , cnt; }Table[maxm]; int size; map<int,int>mp; map<int,string> mmp; queue<int> que; void init() { mp.clear(),mmp.clear(); while(!que.empty())que.pop(); for(int i = 0 ; i < maxm ; ++i) { memset(Table[i].next , 0 , sizeof(Table[i].next)); Table[i].fail = Table[i].cnt = 0; } size = 1; } void insert(char *S) { int n = strlen(S) , now = 0; for (int i = 0 ; i < n ; ++i) { char c = S[i]; if(!Table[now].next[c - ‘a‘]) Table[now].next[c - ‘a‘] = size++; now = Table[now].next[c - ‘a‘]; } Table[now].cnt++; mmp[now]=S; } void build() { Table[0].fail = -1; que.push(0); while (!que.empty()) { int u = que.front(); que.pop(); for (int i = 0; i < 26; ++i) { if(Table[u].next[i]) { if(u == 0) { Table[Table[u].next[i]].fail = 0; } else { int v = Table[u].fail; while(v != -1) { if(Table[v].next[i]) { Table[Table[u].next[i]].fail = Table[v].next[i]; break; } v = Table[v].fail; } if(v == -1)Table[Table[u].next[i]].fail = 0; } que.push(Table[u].next[i]); } } } } void Get(int u) { while (u) { if(Table[u].cnt)mp[u]++; u = Table[u].fail; } } void match(char *S) { int len = strlen(S), now = 0; for (int i = 0; i < len; ++i) { char c = S[i]; if (Table[now].next[c - ‘a‘]) now = Table[now].next[c - ‘a‘]; else { int p = Table[now].fail; while (p != -1 && !Table[p].next[c - ‘a‘]) p = Table[p].fail; if(p == -1) now = 0; else now = Table[p].next[c - ‘a‘]; } if (Table[now].cnt) Get(now); } } void solve() { if(!mp.size()) { printf("0\n"); for(map<int,string>::iterator x=mmp.begin();x!=mmp.end();++x) { for(int i=0;i<Table[x->first].cnt;++i) { cout << x->second << endl; } } return; } int mx=0; vector<int> g; for(map<int,int>::iterator it=mp.begin();it!=mp.end();++it) { if(it->second > mx) { g.clear(); mx=it->second; g.push_back(it->first); } else if(it->second==mx) g.push_back(it->first); } printf("%d\n",mx); for(auto x:g) { auto it=mmp.find(x); for(int i=0;i<Table[x].cnt;++i) { cout <<it->second<< endl; } } } }aho; int T, N; char S[maxn]; int main() { //freopen("in.txt","r",stdin); while(~scanf("%d" , &N),N) { aho.init(); for(int i = 0; i < N; ++i) { scanf("%s" , S); aho.insert(S); } aho.build(); scanf("%s" , S); aho.match(S); aho.solve(); } return 0; }
UVALive 4670 Dominating Patterns
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。