HDU 2222 AC自动机 入门题

本文主要是介绍HDU 2222 AC自动机 入门题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

第一次写AC自动机……

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#define sf scanf
#define pf printf
using namespace std;
const int sigma_size = 26;
struct Trie_Node{int value;//单词节点计数 其他为0struct Trie_Node* next[sigma_size];struct Trie_Node* fail;//失配跳转指针  没有最大前后缀则为rootchar ch;
};typedef struct Trie_Node* poi_node;
poi_node root;
poi_node make_node(char ch){poi_node node = new Trie_Node;node -> value = 0;node -> fail = NULL;node -> ch = ch;for(int i = 0;i < sigma_size;++i){node -> next[i] = NULL;}return node;
}
void Insert(char* s){int len = strlen(s);poi_node cur = root;for(int i = 0;i < len;++i){int idx = s[i] - 'a';if(cur -> next[idx] == NULL){cur -> next[idx] = make_node(idx + 'a');}cur = cur -> next[idx];}cur -> value++;return;
}void get_fail(){queue<poi_node> q;q.push(root);while( !q.empty() ){poi_node cur = q.front();q.pop();for(int i = 0;i < sigma_size;++i){if(cur -> next[i]){poi_node p = cur -> fail;while(p && !p -> next[i]) p = p -> fail;cur -> next[i] -> fail = p ? p -> next[i] : root;q.push(cur -> next[i]);}}}
}int Search(char* s){int len = strlen(s);int ans = 0;poi_node cur = root;for(int i = 0;i < len;++i){int idx = s[i] - 'a';if(cur -> next[idx] == NULL){ //失配poi_node f = cur;while(f && !f -> next[idx]){f = f -> fail;}cur = f ? f -> next[idx] : root;}else cur = cur -> next[idx];ans += cur -> value;if(cur -> value > 0){cur -> value = 0;poi_node p = cur -> fail;while(p){ans += p -> value;p -> value = 0;p = p -> fail;}}}return ans;
}void DFS(poi_node ROOT){for(int i = 0;i < sigma_size;++i){if(ROOT -> next[i] != NULL) DFS(ROOT->next[i]);}delete ROOT;
}
char word[60];
char line[1000000 + 5];
int main(){int T;sf("%d",&T);while(T--){root = make_node('#');int n;sf("%d",&n);for(int i = 0;i < n;++i){sf("%s",word);Insert(word);}sf("%s",line);get_fail();pf("%d\n",Search(line));DFS(root);}return 0;
}

这篇关于HDU 2222 AC自动机 入门题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---