hdu 1277 全文检索 (直接映射查找 || 自动机)

Problem - 1277

　　无聊做水题的时候发现的一道题目。这道题第一反应可以用自动机来解决。当然，条件是各种限制，从而导致可以用直接映射标记的方法来搜索。具体的做法就像RK算法一样，将字符串hash成一个数，这里每一个关键字前四位都是不同的，这样就有利于hash搜索了。当前四位匹配的时候，就可以搜索整个串是否完全匹配。这整个的复杂度大概是O(n*m)，n是全文测长度，m是关键字的长度。

自动机代码：

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <string>

 #include <queue>

 #include <set>

 using namespace std;

 const int kind = ;

 struct Node {

     Node *next[kind];

     Node *fail;

     string label;

     Node() {

         memset(next, , sizeof(next));

         fail = NULL;

         label = "";

     }

     Node(char *tmp) {

         memset(next, , sizeof(next));

         fail = NULL;

         label = tmp;

     }

 } ;

 struct Trie {

     Node *Root;

     Trie() { Root = new Node();}

     void insert(char *s, char *label) {

         Node *p = Root;

         while (*s) {

             int idx = *s - '';

             if (!p->next[idx]) {

                 p->next[idx] = new Node();

                 p->next[idx]->fail = p;

             }

             p = p->next[idx];

             s++;

         }

         p->label = label;

     }

     void build() {

         queue<Node *> Q;

         while (!Q.empty()) Q.pop();

         Q.push(Root);

         Root->fail = NULL;

         Node *cur, *p;

         while (!Q.empty()) {

             cur = Q.front();

             Q.pop();

             for (int i = ; i < kind; i++) {

 //                cout << cur->next[i] << ' ';

                 if (cur->next[i]) {

 //                    cout << i << ' ';

                     Q.push(cur->next[i]);

                     p = cur->fail;

                     while (p) {

                         if (p->next[i]) {

                             cur->next[i]->fail = p->next[i];

                             break;

                         }

                         p = p->fail;

                     }

                     if (!p) cur->next[i]->fail = Root;

                 }

             }

         }

     }

     void query(char *s) {

         set<string> vis;

         bool pnt = false;

         Node *cur = Root;

         while (*s) {

             int idx = *(s++) - '';

             while (cur && !cur->next[idx]) cur = cur->fail;

             cur = cur ? cur->next[idx] : Root;

             if (vis.find(cur->label) != vis.end()) continue;

             if (cur->label.length()) {

                 if (!pnt) {

                     printf("Found key:");

                     pnt = true;

                 }

                 cout << ' ' << cur->label;

                 vis.insert(cur->label);

             }

         }

         if (!pnt) puts("No key can be found !");

         cout << endl;

     }

 } trie;

 char str[], buf[];

 int main() {

 //    freopen("in", "r", stdin);

     int n, m;

     while (cin >> n >> m) {

         trie = Trie();

         gets(buf);

         str[] = ;

         while (n-- && gets(buf)) strcat(str, buf);

         gets(buf);

         while (m-- && gets(buf)) {

             char *p = buf;

             while (*(p++) != ']') ;

             *(p++) = ;

             while (*p == ' ') p++;

             trie.insert(p, buf);

 //            cout << p << ' ' << buf << " inserted!"<< endl;

         }

         trie.build();

 //        cout << "built!!" << endl;

         trie.query(str);

     }

     return ;

 }

UPD：

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <string>

 using namespace std;

 const int HASHLEN = ;

 const int M = ;

 const int N = ;

 string label[N], key[N];

 bool vis[N];

 int id[M];

 char str[ * N], buf[N];

 bool check(int t, char *p) {

     int len = key[t].length();

     for (int i = ; i < len; i++) {

         if (key[t][i] != p[i]) return false;

     }

     return true;

 }

 void work(char *p) {

     bool pnt = false;

     char *q = p;

     int cur = , ep = ;

     for (int i = ; i < HASHLEN - ; i++) cur = cur *  + *(q++) - '', ep *= ;

     while (*q && *p) {

 //        cout << cur << endl;

         cur = cur *  + *q - '';

         cur %= ep;

         int t = id[cur];

         if (t != - && !vis[t]) {

             if (check(t, p)) {

                 if (!pnt) printf("Found key:");

                 pnt = vis[t] = true;

                 cout << ' ' << label[t];

             }

         }

         p++, q++;

     }

     if (!pnt) printf("No key can be found !");

     cout << endl;

 }

 int main() {

 //    freopen("in", "r", stdin);

     int n, m;

     while (cin >> n >> m) {

         memset(id, -, sizeof(id));

         memset(vis, , sizeof(vis));

         gets(buf);

         str[] = ;

         while (n-- && gets(buf)) strcat(str, buf);

         gets(buf);

         for (int i = ; i < m; i++) {

             gets(buf);

             char *p = buf;

             while (*p && *p != ']') p++;

             *(++p) = ;

             p++;

             while (*p && *p == ' ') p++;

             label[i] = buf;

             key[i] = p;

 //            cout << label[i] << ' ' << key[i] << endl;

             int cid = ;

             for (int i = ; i < HASHLEN; i++) cid = cid *  + p[i] - '';

 //            cout << cid << endl;

             if (id[cid] != -) { puts("shit!"); while () ;}

             id[cid] = i;

         }

         work(str);

     }

     return ;

 }

　　不知道为什么这个代码能过G++但是C++过不了，应该是代码里面有bug。另外，数据似乎跟描述的有点出入，说好的不同key值的前四位不会相同，可是写了句来试它的数据时就发现被骗了，所以后来用了5位，过了！

——written by Lyon