aho_corasick.h

00001 /*
00002  * ASTL - the Automaton Standard Template Library.
00003  * C++ generic components for Finite State Automata handling.
00004  * Copyright (C) 2000-2003 Vincent Le Maout (vincent.lemaout@chello.fr).
00005  * 
00006  * This library is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Lesser General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2.1 of the License, or (at your option) any later version.
00010  * 
00011  * This library is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Lesser General Public License for more details.
00015  * 
00016  * You should have received a copy of the GNU Lesser General Public
00017  * License along with this library; if not, write to the Free Software
00018  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
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 // Requirements: A is a tree
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 } // namespace astl
00056 
00057 #endif // ASTL_AHO_CORASICK_H
00058 
00059 
00060 
00061 
00062 
00063 

Generated on Sun Mar 8 02:41:30 2009 for ASTL by  doxygen 1.5.7.1