首页 > 代码库 > zoj 3228 - Searching the String
zoj 3228 - Searching the String
题目:给你一个长目标串str,和一些模式串,求每个串出现的次数。模式串有可覆盖和不可覆盖两种。
分析:字符串,多串匹配,AC自动机。由于数据有可能不允许相交,所以记录上一个的结束位置。
题目的数据比较猥琐,可能相同,采用一个 Fath域记录第一次出现的 id,计算一次就可以了。
说明:注意数据有相同的串;该题可以使用 RK算法+二分。
#include <stdio.h> #include <stdlib.h> #include <string.h> char Word[10]; char Line[100005]; int Walk[100005]; int Fath[100005]; /* AC_DFA define */ #define nodesize 300005 #define dictsize 26 typedef struct node { int flag[2]; int last; int deep; node* fail; node* next[dictsize]; }tnode; tnode dict[nodesize]; tnode* Q[nodesize]; int ID[256]; class AC_DFA { private: int size; tnode* root; public: AC_DFA() {makeID();init();} void makeID() { for (int i = 0 ; i < dictsize ; ++ i) ID[i+'a'] = i; } void init() { memset(dict, 0, sizeof(dict)); root=NULL;size=0;root=newnode(); } tnode* newnode() { dict[size].fail = root; dict[size].last = -1; return &dict[size ++]; } void insert(char* word, int id, int s) { tnode* now = root; for (int i = 0 ; word[i] ; ++ i) { if (!now->next[ID[word[i]]]) now->next[ID[word[i]]] = newnode(); now = now->next[ID[word[i]]]; } /* 记录数据,相同的计入父节点 */ if (!now->flag[s]) { now->deep = strlen(word); now->flag[s] = id; }else Fath[id] = now->flag[s]; } void setfail() { Q[0] = root; root->fail = NULL; for (int move = 0,save = 1 ; move < save ; ++ move) { tnode* now = Q[move]; for (int i = 0 ; i < dictsize ; ++ i) if (now->next[i]) { tnode* p = now->fail; while (p && !p->next[i]) p = p->fail; now->next[i]->fail = p?p->next[i]:root; Q[save ++] = now->next[i]; }else now->next[i] = now==root?root:now->fail->next[i];//构建 Trie图 } } int query(char* line, int N) { memset(Walk, 0, sizeof(Walk)); tnode* now = root; for (int i = 0 ; line[i] ; ++ i) { now = now->next[ID[line[i]]]; for (tnode* p = now ; p ; p = p->fail) { if (p->flag[0]) ++ Walk[p->flag[0]]; if (p->flag[1] && p->last+p->deep <= i) { p->last = i; ++ Walk[p->flag[1]]; } } } for (int i = 1 ; i <= N ; ++ i) printf("%d\n",Walk[Fath[i]]); return 0; } }; /* AC_DFA end */ int main() { int N,S,T = 1; AC_DFA ac; while (scanf("%s",Line) != EOF) { ac.init(); scanf("%d",&N); for (int i = 1 ; i <= N ; ++ i) { scanf("%d %s",&S,Word); Fath[i] = i; ac.insert(Word, i, S); } ac.setfail(); printf("Case %d\n",T ++); ac.query(Line, N); printf("\n"); } return 0; }
zoj 3228 - Searching the String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。