[Data Structure] Automatic machine for multiple target strings matching - automaton, Data Structure, for, matching, multiple, search, strings, targets

Based on the number of tries, the suffix automaton introduces the parent node parent, prefix nxt, subsequent child[], matching The number of words cnt, where child[i] is the node to jump to when the current string encounters char i. The following content can use bfs to initialize automata from shallow to deep. This process is similar to kmp, I think the difference is that kmp does not save the jump position of each node after encountering any letter, but only saves the position where it matches the prefix string (nxt) as follows: Note that n#parent has been initialized.

if n#parent!=root(ie n#parent#nxt!=n#parent)

n#nxt=node[n#parent#nxt].child[n#idx]

if n#child[i]==null

n#child[i]=node[n#nxt]->child[i]

n#cnt+=node[n#nxt].cnt

#include #include #include #include #define MAXLEN 1100000#define CHILDCNT 26using namespace std;struct Node{ int idx; int nxt; int pnt; int child[CHILDCNT]; int cnt;// words matched void init(int parent,int childIdx){ idx=childIdx; nxt=0,pnt=parent,cnt=0; memset(child,0,sizeof(child)); });struct TrieG{ //int root=0; Node nodes[MAXLEN]; int lst; TrieG(){ lst=0; nodes[lst++].init(0 ,0);} string print(int i){ if(i==0) return ""; Node &n=nodes[i]; char c='a'+n.idx; return print(n.pnt)+ c;} void add(char* s){ int v=0; int len=strlen(s); for(int i=0;ique; que.push(0); while(!que.empty()){ int v=que.front();que.pop(); Node &n=nodes[v]; for(int i=0 ;i0) {if(n.pnt>0) n.nxt=nodes [nodes[n.pnt].nxt].child[n.idx]; n.cnt+=nodes[n.nxt].cnt; for(int i=0;ichild["< >n; char buf[1000001]; for(int i=0;i>buf; g.add(buf);} g.init(); cin>>buf; bool res= g.match(buf); if(res) cout<<"YES"<

Leave a Comment Cancel reply