[UVA1449] Dominating Patterns（AC自动机，STL，计数，神坑）

题目链接：https://vjudge.net/problem/UVA-1449

题意：给一个词典和一个字符串，找出字符串里出现次数最多的单词，如果有出现次数相同的，要按照输入顺序输出。

坑点好多，或许是因为自己实现得比较挫所以坑才多。

用一个map<string,int>计数，map<string,vector<int>>记录同样的字符串出现的位置，map<string,int> p记录id，string数组记录对应id下的字符串。

查询的时候注意假如字符串中并没有出现词典中的单词，输出0，要按顺序把所有字符串打印出来。

太菜了，这个坑WA了十发。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 
  5 typedef pair<int, int> pii;
  6 typedef pair<int, string> pis;
  7 const int maxn = 155;
  8 const int maxm = 1000100;
  9 map<string, int> vis;
 10 map<string, vector<int>> id;
 11 map<string, int> p;
 12 string qq[maxn];
 13 int pcnt;
 14 
 15 typedef class Node {
 16 public:
 17     Node *next[26];
 18     Node *fail;
 19     int flag;
 20     int id;
 21     Node() {
 22         memset(next, 0, sizeof(next));
 23         fail = NULL;
 24         flag = 0;
 25         id = -1;
 26     }
 27 }Node;
 28 
 29 class AC_Automation {
 30 public:
 31     Node *root;
 32     queue <Node*> q;
 33     AC_Automation() {
 34         root = new Node();
 35         while(!q.empty()) q.pop();
 36     }
 37     void insert(string s) {
 38         Node *cur = root;
 39         int len = s.length();
 40         for(int i = 0; i < len; i++) {
 41             int index = s[i] - 'a';
 42             if(cur->next[index] == NULL) {
 43                 cur->next[index] = new Node();
 44             }
 45             cur = cur->next[index];
 46         }
 47         cur->id = p[s]; cur->flag = 1;
 48     }
 49     void BuildAC() {
 50         Node *cur, *tmp;
 51         q.push(root);
 52         while(!q.empty()) {
 53             cur = q.front();
 54             q.pop();
 55             for(int i = 0; i < 26; i++) {
 56                 if(!cur->next[i]) continue;
 57                 if(cur == root) {
 58                     cur->next[i]->fail = root;
 59                 }
 60                 else {
 61                     tmp = cur->fail;
 62                     while(tmp != NULL) {
 63                         if(tmp->next[i]) {
 64                             cur->next[i]->fail = tmp->next[i];
 65                             break;
 66                         }
 67                         tmp = tmp->fail;
 68                     } 
 69                     if(tmp == NULL) {
 70                         cur->next[i]->fail = root;
 71                     }
 72                 }
 73                 q.push(cur->next[i]);
 74             }
 75         }
 76     }
 77     void query(string s) {
 78         Node *cur = root, *tmp;
 79         int len = s.length();
 80         for(int i = 0; i < len; i++) {
 81             int index = s[i] - 'a';
 82             while(cur->next[index] == NULL && cur != root) {
 83                 cur = cur->fail;
 84             }
 85             cur = cur->next[index];
 86             if(cur == NULL) {
 87                 cur = root;
 88                 continue;
 89             }
 90             tmp = cur;
 91             while(tmp != root) {
 92                 if(tmp->flag) vis[qq[tmp->id]]++;
 93                 tmp = tmp->fail;
 94             }
 95         }
 96         int maxx = 0;
 97         vector<pis> ret;
 98         for(auto it : vis) maxx = max(maxx, it.second);
 99         for(auto it : vis) {
100             if(it.second == maxx) {
101                 for(auto itt : id[it.first]) {
102                     ret.push_back(pis(itt, it.first));
103                 }
104             }
105         }
106         sort(ret.begin(), ret.end());
107         printf("%d
", maxx);
108         if(maxx != 0) {
109             for(auto it : ret) {
110                 printf("%s
", it.second.c_str());
111             }
112         }
113         else {
114             for(int i = 0; i < pcnt; i++) {
115                 printf("%s
", qq[i].c_str());
116             }
117         }
118     }
119 };
120 
121 char pat[maxn], tar[maxm];
122 int n;
123 
124 int main() {
125     // freopen("in", "r", stdin);
126     while(~scanf("%d", &n) && n) {
127         id.clear(); p.clear(); vis.clear();
128         pcnt = 0;
129         AC_Automation ac = AC_Automation();
130         for(int i = 1; i <= n; i++) {
131             scanf("%s", pat);
132             if(p.find(pat) == p.end()) {
133                 qq[pcnt] = pat;
134                 p[pat] = pcnt++;
135             }
136             id[pat].push_back(i);
137             ac.insert(pat);
138         }
139         ac.BuildAC();
140         scanf("%s", tar);
141         ac.query(tar);
142     }
143     return 0;
144 }