HDU 2896 AC自动机模式串匹配

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

题目链接

题意：查找主串中出现的模式串并输出模式串的编号
模板题

顺便提一下杭电的G++编译要比C++编译内存占用多得多
而且杭电oj判内存使用的规则为整个过程一共开辟的新的空间而不是峰值空间在使用动态开辟空间时以后可能会用到的空间都不要删除使用这里的动态字典树没有删除任何节点仅仅初始化了空间

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <set>
#define sf scanf
#define pf printf
using namespace std;
const int sigma_size = 100;
typedef struct Trie_Node* poi_Node;
struct Trie_Node{int v;poi_Node next[sigma_size];poi_Node fail;
};
poi_Node root;
poi_Node make_node(){poi_Node cur = new Trie_Node;cur -> v = 0;memset(cur -> next,NULL,sizeof(cur -> next));cur -> fail = NULL;return cur;
}
void Insert(char* s,int v){int len = strlen(s);poi_Node cur = root;for(int i = 0;i < len;++i){int idx = s[i] - 32;if(cur -> next[idx] == NULL){cur -> next[idx] = make_node();}cur = cur -> next[idx];}cur -> v = v;
}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]);}}}
}set<int> ans;
bool Search(char* s,int lable){int len = strlen(s);int cnt = 0;poi_Node cur = root;for(int i = 0;i < len;++i){int idx = s[i] - 32;if(cur -> next[idx] == NULL){while(cur && cur -> next[idx] == NULL) cur = cur -> fail;if(cur == NULL) cur = root;else cur = cur -> next[idx];}else cur = cur -> next[idx];if(cur -> v > 0){ans.insert(cur -> v);}poi_Node p = cur;while(p){if(p -> v > 0){ans.insert(p -> v);}p = p -> fail;}}cnt = ans.size();if(cnt){pf("web %d:",lable);for(set<int>::iterator it = ans.begin();it != ans.end();++it){pf(" %d",*it);}pf("\n");}return cnt > 0;
}void DFS(poi_Node ROOT){for(int i = 0; i < sigma_size;++i) if(ROOT -> next[i]) DFS(ROOT -> next[i]);ROOT -> v = 0;
}char str[10000 + 5];
int main(){
//    freopen("read.txt","r",stdin);int n,m;while( sf("%d",&n) != EOF ){root = make_node();for(int i = 0;i < n;++i){sf("%s",str);Insert(str,i + 1);}get_fail();sf("%d",&m);int cnt = 0;for(int i = 0;i < m;++i){ans.clear();sf("%s",str);cnt += Search(str,i + 1);}pf("total: %d\n",cnt);DFS(root);}return 0;
}