首页 > 代码库 > HDU5880 Family View(AC自动机)
HDU5880 Family View(AC自动机)
题意:将匹配的串用‘*’代替
tips:
1 注意内存的使用,据说g++中指针占8字节,c++4字节,所以用g++交会MLE
2 注意这种例子,
1
2
abcd
bc
abc
故失败指针要一直往下走,否则会丢弃一些串
3 当出现非英文字符时应先将指针指向根节点,否则出现
1
1
cy
c,,,,,,,y
时结果为c,,,,,,**(由不止一种Bug造成的),正确的应为c,,,,,,,y,然而很多题解这样也过了~
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<utility> using namespace std; typedef long long LL; int Hash[128]; const int N = 1000008, CH = 26; struct Trie{ Trie *next[CH]; Trie *fail; int len; }; int flag[N]; char str[N]; class ACauto{ Trie tree[N]; private: int nxt; Trie *root; public: void init(){ root = &tree[0]; nxt=0; memset(&tree[0], 0, sizeof(Trie)); memset(flag, 0, sizeof(flag)); } void insert(char *s){ Trie *p = root; int i; for(i = 0; s[i]; i++){ int c = Hash[s[i]]; if(!p -> next[c]){ memset(&tree[++nxt], 0, sizeof(Trie)); p -> next[c] = &tree[nxt]; } p = p -> next[c]; } //p -> cnt = 1; //p -> cnt++;//用于统计 p -> len = i; } void build(){ queue<Trie *> q; q.push(root); root -> fail = NULL; while(!q.empty()){ Trie *now = q.front(); q.pop(); for(int i = 0; i < CH; i++){ Trie *son = now -> next[i]; Trie *tp = (now == root)? root: now -> fail->next[i]; if(son == NULL){ now -> next[i] = tp;//Trie图 }else{ son -> fail = tp; //状态合并(如一个串是另一个串的子串则值域可以合并) //son -> cnt += son -> fail -> cnt; q.push(son); } } } } //查询匹配次数 void query(char *s){ Trie *now = root; for(int i = 0; s[i]; i++){ int c = Hash[s[i]]; if(c == -1){ //注意,要将now赋值为root now = root; continue; } now = now -> next[c]; Trie *p = now; while(p != root){ if(p -> len){ flag[i - p -> len + 1]--; flag[i + 1]++; } p = p -> fail; } } } }ac; int main(){ fill(Hash, Hash + 128, -1); for(int i = ‘a‘; i <= ‘z‘; i++){ Hash[i] = i - ‘a‘; } for(int i = ‘A‘; i <= ‘Z‘; i++){ Hash[i] = i - ‘A‘; } int t; cin >>t; while(t--){ ac.init(); int n; scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%s", str); ac.insert(str); } ac.build(); getchar(); gets(str); ac.query(str); LL cnt = 0; for(int i = 0; str[i]; i++){ cnt += flag[i]; if(cnt >= 0){ putchar(str[i]); }else{ putchar(‘*‘); } } printf("\n"); } return 0; }
HDU5880 Family View(AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。