Artifact 71f65eb207acadc5111ef3d876f996bf55ab2ca3:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 41 68 6f 2d 43 6f 72 61 73 69 63 6b 20 // Aho-Corasick
0050: 6d 75 6c 74 69 20 70 61 74 74 65 72 6e 20 73 65 multi pattern se
0060: 61 72 63 68 0a 2f 2f 20 20 20 4f 28 7c 73 69 7a arch.// O(|siz
0070: 65 2d 6f 66 2d 70 61 74 74 65 72 6e 73 7c 29 20 e-of-patterns|)
0080: 66 6f 72 20 63 6f 6e 73 74 72 75 63 74 69 6f 6e for construction
0090: 2e 20 4f 28 31 29 20 70 65 72 20 73 74 65 70 2e . O(1) per step.
00a0: 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 .//.// Verified
00b0: 62 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 35 31 39 by.// - SRM519
00c0: 20 44 69 76 31 20 4c 56 32 0a 2f 2f 2d 2d 2d 2d Div1 LV2.//----
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 74 65 6d 70 6c ---------..templ
0110: 61 74 65 3c 69 6e 74 20 4e 43 3d 32 36 2c 20 63 ate<int NC=26, c
0120: 68 61 72 20 42 43 3d 27 61 27 3e 0a 73 74 72 75 har BC='a'>.stru
0130: 63 74 20 41 68 6f 43 6f 72 61 73 69 63 6b 0a 7b ct AhoCorasick.{
0140: 0a 09 41 68 6f 43 6f 72 61 73 69 63 6b 28 20 63 ..AhoCorasick( c
0150: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 73 74 72 69 onst vector<stri
0160: 6e 67 3e 26 20 70 20 29 20 3a 20 6c 69 6e 6b 28 ng>& p ) : link(
0170: 4e 43 2b 31 29 20 7b 0a 09 09 2f 2f 20 43 72 65 NC+1) {...// Cre
0180: 61 74 65 20 61 20 74 72 69 65 0a 09 09 66 6f 72 ate a trie...for
0190: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 70 2e 73 69 (int i=0; i<p.si
01a0: 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 ze(); ++i) {....
01b0: 41 68 6f 43 6f 72 61 73 69 63 6b 2a 20 74 20 3d AhoCorasick* t =
01c0: 20 74 68 69 73 3b 0a 09 09 09 66 6f 72 28 69 6e this;....for(in
01d0: 74 20 6b 3d 30 3b 20 6b 3c 70 5b 69 5d 2e 73 69 t k=0; k<p[i].si
01e0: 7a 65 28 29 3b 20 74 3d 74 2d 3e 6c 69 6e 6b 5b ze(); t=t->link[
01f0: 70 5b 69 5d 5b 6b 2b 2b 5d 2d 42 43 5d 29 0a 09 p[i][k++]-BC])..
0200: 09 09 09 69 66 28 21 74 2d 3e 6c 69 6e 6b 5b 70 ...if(!t->link[p
0210: 5b 69 5d 5b 6b 5d 2d 42 43 5d 29 0a 09 09 09 09 [i][k]-BC]).....
0220: 09 74 2d 3e 6c 69 6e 6b 5b 70 5b 69 5d 5b 6b 5d .t->link[p[i][k]
0230: 2d 42 43 5d 3d 6e 65 77 20 41 68 6f 43 6f 72 61 -BC]=new AhoCora
0240: 73 69 63 6b 3b 0a 09 09 09 74 2d 3e 66 69 6e 61 sick;....t->fina
0250: 6c 2e 69 6e 73 65 72 74 28 69 29 3b 0a 09 09 7d l.insert(i);...}
0260: 0a 0a 09 09 2f 2f 20 44 6f 20 42 46 53 20 61 6e ....// Do BFS an
0270: 64 20 64 72 61 77 20 66 61 69 6c 75 72 65 20 6c d draw failure l
0280: 69 6e 6b 73 2c 20 61 6e 64 20 70 72 65 70 61 72 inks, and prepar
0290: 65 20 66 6f 72 20 73 75 62 73 74 72 69 6e 67 20 e for substring
02a0: 70 61 74 74 65 72 6e 0a 09 09 71 75 65 75 65 3c pattern...queue<
02b0: 41 68 6f 43 6f 72 61 73 69 63 6b 2a 3e 20 51 3b AhoCorasick*> Q;
02c0: 0a 09 09 66 6f 72 28 69 6e 74 20 63 3d 30 3b 20 ...for(int c=0;
02d0: 63 3c 4e 43 3b 20 2b 2b 63 29 0a 09 09 09 69 66 c<NC; ++c)....if
02e0: 28 20 6c 69 6e 6b 5b 63 5d 20 29 20 7b 0a 09 09 ( link[c] ) {...
02f0: 09 09 51 2e 70 75 73 68 28 6c 69 6e 6b 5b 63 5d ..Q.push(link[c]
0300: 29 3b 0a 09 09 09 09 6c 69 6e 6b 5b 63 5d 2d 3e );.....link[c]->
0310: 6c 69 6e 6b 5b 4e 43 5d 20 3d 20 74 68 69 73 3b link[NC] = this;
0320: 20 2f 2f 20 22 63 22 27 73 20 73 75 66 66 69 78 // "c"'s suffix
0330: 20 69 73 20 22 22 0a 09 09 09 09 6c 69 6e 6b 5b is "".....link[
0340: 63 5d 2d 3e 66 69 6e 61 6c 2e 69 6e 73 65 72 74 c]->final.insert
0350: 28 66 69 6e 61 6c 2e 62 65 67 69 6e 28 29 2c 20 (final.begin(),
0360: 66 69 6e 61 6c 2e 65 6e 64 28 29 29 3b 0a 09 09 final.end());...
0370: 09 7d 0a 09 09 09 65 6c 73 65 0a 09 09 09 09 6c .}....else.....l
0380: 69 6e 6b 5b 63 5d 20 3d 20 74 68 69 73 3b 0a 09 ink[c] = this;..
0390: 09 77 68 69 6c 65 28 20 21 51 2e 65 6d 70 74 79 .while( !Q.empty
03a0: 28 29 20 29 20 7b 0a 09 09 09 41 68 6f 43 6f 72 () ) {....AhoCor
03b0: 61 73 69 63 6b 2a 20 74 3d 51 2e 66 72 6f 6e 74 asick* t=Q.front
03c0: 28 29 3b 20 51 2e 70 6f 70 28 29 3b 0a 09 09 09 (); Q.pop();....
03d0: 66 6f 72 28 69 6e 74 20 63 3d 30 3b 20 63 3c 4e for(int c=0; c<N
03e0: 43 3b 20 2b 2b 63 29 0a 09 09 09 09 69 66 28 20 C; ++c).....if(
03f0: 74 2d 3e 6c 69 6e 6b 5b 63 5d 20 29 20 7b 0a 09 t->link[c] ) {..
0400: 09 09 09 09 51 2e 70 75 73 68 28 74 2d 3e 6c 69 ....Q.push(t->li
0410: 6e 6b 5b 63 5d 29 3b 0a 09 09 09 09 09 41 68 6f nk[c]);......Aho
0420: 43 6f 72 61 73 69 63 6b 2a 20 72 20 3d 20 74 2d Corasick* r = t-
0430: 3e 6c 69 6e 6b 5b 4e 43 5d 3b 20 2f 2f 20 22 72 >link[NC]; // "r
0440: 22 20 69 73 20 73 75 66 66 69 78 20 6f 66 20 22 " is suffix of "
0450: 74 22 2e 2e 2e 0a 09 09 09 09 09 77 68 69 6c 65 t".........while
0460: 28 20 21 72 2d 3e 6c 69 6e 6b 5b 63 5d 20 29 0a ( !r->link[c] ).
0470: 09 09 09 09 09 09 72 20 3d 20 72 2d 3e 6c 69 6e ......r = r->lin
0480: 6b 5b 4e 43 5d 3b 0a 09 09 09 09 09 74 2d 3e 6c k[NC];......t->l
0490: 69 6e 6b 5b 63 5d 2d 3e 6c 69 6e 6b 5b 4e 43 5d ink[c]->link[NC]
04a0: 20 3d 20 72 2d 3e 6c 69 6e 6b 5b 63 5d 3b 20 2f = r->link[c]; /
04b0: 2f 20 74 68 65 6e 20 22 72 63 22 20 69 73 20 73 / then "rc" is s
04c0: 75 66 66 69 78 20 6f 66 20 22 74 63 22 0a 09 09 uffix of "tc"...
04d0: 09 09 09 74 2d 3e 6c 69 6e 6b 5b 63 5d 2d 3e 66 ...t->link[c]->f
04e0: 69 6e 61 6c 2e 69 6e 73 65 72 74 28 72 2d 3e 6c inal.insert(r->l
04f0: 69 6e 6b 5b 63 5d 2d 3e 66 69 6e 61 6c 2e 62 65 ink[c]->final.be
0500: 67 69 6e 28 29 2c 20 72 2d 3e 6c 69 6e 6b 5b 63 gin(), r->link[c
0510: 5d 2d 3e 66 69 6e 61 6c 2e 65 6e 64 28 29 29 3b ]->final.end());
0520: 0a 09 09 09 09 7d 0a 09 09 7d 0a 09 7d 0a 09 63 .....}...}..}..c
0530: 6f 6e 73 74 20 41 68 6f 43 6f 72 61 73 69 63 6b onst AhoCorasick
0540: 2a 20 73 74 61 72 74 28 29 20 63 6f 6e 73 74 20 * start() const
0550: 7b 20 72 65 74 75 72 6e 20 74 68 69 73 3b 20 7d { return this; }
0560: 0a 09 63 6f 6e 73 74 20 41 68 6f 43 6f 72 61 73 ..const AhoCoras
0570: 69 63 6b 2a 20 6e 65 78 74 28 63 68 61 72 20 63 ick* next(char c
0580: 29 20 63 6f 6e 73 74 20 7b 0a 09 09 63 6f 6e 73 ) const {...cons
0590: 74 20 41 68 6f 43 6f 72 61 73 69 63 6b 2a 20 74 t AhoCorasick* t
05a0: 20 3d 20 74 68 69 73 3b 0a 09 09 77 68 69 6c 65 = this;...while
05b0: 28 20 21 74 2d 3e 6c 69 6e 6b 5b 63 2d 42 43 5d ( !t->link[c-BC]
05c0: 20 29 0a 09 09 09 74 20 3d 20 74 2d 3e 6c 69 6e )....t = t->lin
05d0: 6b 5b 4e 43 5d 3b 0a 09 09 72 65 74 75 72 6e 20 k[NC];...return
05e0: 74 2d 3e 6c 69 6e 6b 5b 63 2d 42 43 5d 3b 0a 09 t->link[c-BC];..
05f0: 7d 0a 09 63 6f 6e 73 74 20 73 65 74 3c 69 6e 74 }..const set<int
0600: 3e 26 20 61 63 63 65 70 74 28 29 20 63 6f 6e 73 >& accept() cons
0610: 74 20 7b 20 72 65 74 75 72 6e 20 66 69 6e 61 6c t { return final
0620: 3b 20 7d 0a 09 7e 41 68 6f 43 6f 72 61 73 69 63 ; }..~AhoCorasic
0630: 6b 28 29 20 7b 20 66 6f 72 28 69 6e 74 20 69 3d k() { for(int i=
0640: 30 3b 20 69 3c 4e 43 3b 20 2b 2b 69 29 20 69 66 0; i<NC; ++i) if
0650: 28 6c 69 6e 6b 5b 69 5d 21 3d 74 68 69 73 29 20 (link[i]!=this)
0660: 64 65 6c 65 74 65 20 6c 69 6e 6b 5b 69 5d 3b 20 delete link[i];
0670: 7d 0a 70 72 69 76 61 74 65 3a 0a 09 41 68 6f 43 }.private:..AhoC
0680: 6f 72 61 73 69 63 6b 28 29 20 3a 20 6c 69 6e 6b orasick() : link
0690: 28 4e 43 2b 31 29 20 7b 7d 0a 09 76 65 63 74 6f (NC+1) {}..vecto
06a0: 72 3c 41 68 6f 43 6f 72 61 73 69 63 6b 2a 3e 20 r<AhoCorasick*>
06b0: 6c 69 6e 6b 3b 0a 09 73 65 74 3c 69 6e 74 3e 20 link;..set<int>
06c0: 66 69 6e 61 6c 3b 0a 7d 3b 0a final;.};.