00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef ASTL_AHO_CORASICK_H
00024 #define ASTL_AHO_CORASICK_H
00025
00026 #include <astl.h>
00027
00028 using namespace std;
00029
00030 namespace astl {
00031
00032
00033 template <typename DFA>
00034 void aho_corasick(DFA &A, const typename DFA::char_type &c)
00035 {
00036 bfirst_cursor<queue_cursor<forward_cursor<DFA> >, set_marker<unsigned int> >
00037 i = bfirst_markc(A), j;
00038 A.set_trans(A.initial(), c, A.initial());
00039 while (i != j) {
00040 do {
00041 if (i.letter() != c) {
00042 forward_cursor<DFA> f(A, i.src());
00043 while (f.forward(c) && f.src() != A.initial() && !f.find(i.letter()));
00044 if (!f.sink() && f.find(i.letter()) && i.aim() != f.aim()) {
00045 A.set_trans(i.aim(), c, f.aim());
00046 A.final(i.aim()) = i.aim_final() || f.aim_final();
00047 }
00048 else
00049 A.set_trans(i.aim(), c, A.initial());
00050 }
00051 } while (i.next());
00052 }
00053 }
00054
00055 }
00056
00057 #endif // ASTL_AHO_CORASICK_H
00058
00059
00060
00061
00062
00063