算法:在一次遍历中搜索多个子串（c++）

问题：存在一个很大的文本文件 fileA.要在这个文件中搜索出现的多个字符串substr1,substr2...。每次搜索到一个子串，调用指定的函数。
要求：（1）只能读取一遍文件.
（2）文件读取过程中，同时完成字符串的匹配。不能预先把文件中的内容加载到内存---文件很大，也不能完全加载到内存中.
（3）编写可重用的代码.
思路：状态机的思路。对每个要搜索的字符串，分配一个状态机。状态机中，使用恰当的数据结构，保存所有可能成功匹配的中间状态，每读取一个字符，更新这个状态机的状态。当状态表现为“成功匹配”，则调用指定的回调函数。

使用一个bool类型的数组state来保存这个状态，当存在state[i]==true，表示，已经成功匹配到第i个字符串。注意：可能存在多个i使state[i]==true，表示多个匹配的中间状态。

设，要搜索的字符串为，'aab'时。 bool数组为 bool state[b].

初始状态为{0,0,0}
(1)输入'a' -> {1,0,0}, 匹配状态, aab
(2)输入'a' -> {1,1,0}, 匹配状态，aab, aab
(3)输入'a' -> {1,1,0}, 匹配状态，aab, aab
(4)输入'b' -> {0,0,1}, 匹配状态, aab 成功匹配 ，调用回调函数，重置最后一位false。->{0,0,0}

注意，如果要匹配'aa', 当出现'aaab'应该视为，可以成功匹配2次。
初始状态{0,0,0}
（1）输入'a' ->{1,0}, 匹配状态，aa
（2）输入'a' ->{1,1}, 匹配状态 aa aa 成功匹配，调用回调函数，重置最后一个位为false。->{1,0}
（3）输入'a' ->{1,1}, 匹配状态 aa aa 成功匹配，调用回调函数，重置最后一个位为false。->{1,0}
（4）输入'b' ->{0,0}
 
当要匹配多个字符串的时候，只需要维护多个上面状态机(使用composite的方法，构造一个更大的状态机)。就可一保存所有的字串的匹配的中间状态。
具体算法实现，参考下面的代码

实现：
1.回调函数.当每次字符串调用成功.调用用户定义的函数。
   

/**
 * 回掉函数类型，当成功匹配是被调用
 *
 * @param substr 要匹配的子字符串
 * @param pos 成功匹配的位置
 * @param user_data 回调函数使用的自定义数据
 */
typedef void (*ok_callback_T)(const char *substr,
                              unsigned int pos,
                              void *user_data);

如：统计指定字符串个数的回调函数，可以使用user_data作为输出参数。
   ok_callback_T count_number;
   

void count_number(const char *substr,
                  unsigned int pos,
                  void *user_data)
{
     (*(unsigned int*)user_data)++;
}

2.实现单个字符串的搜索

class searcher
{
public:
     /**
      * 构造函数
      *
      * @param substr 待匹配的字符串
      * @param cb 成功匹配时调用的回调函数
      * @param user_data 指向用户子定义的数据，这个数据会传递给回掉函数
      * @param case_sensitive 大小写敏感(when true)
      */
     searcher(const char *substr,
              ok_callback_T cb,
              void * user_data = NULL,
              bool case_sensitive = true);
     
     ///追加一个字符
     void feed(char more_ch);
     //... ...
private:
        ///是否大小写敏感
     const bool m_case_sensitive;

     ///记录当前位置
     unsigned int m_pos;

     ///记录要匹配的子串
     char * m_str;

     ///自定义数据
     void * m_user_data;

     ///记录当前的匹配状态数据结构
     std::vector<bool> m_state;

     //... ...
}

算法实现：

void searcher::feed(char more_ch)
{
     //位置移动

     m_pos++;
     if(!m_case_sensitive)
          more_ch = toupper(more_ch);
     
     ///对已经匹配到中途的状态，继续尝试匹配

     for(int i=m_size-2;i>=0; i--)
     {
          if(m_state[i])
          {
               m_state[i] = false;
               if(m_str[i+1] == more_ch)
               {
                    m_state[i+1] = true;
               }
               
          }
     }
     
     ///尝试从开始位置进行匹配

     if(m_str[0] == more_ch)
          m_state[0] = true;
     
     ///发生完整匹配,调用回掉函数

     if(m_state[m_size-1])
     {
          m_state[m_size-1] = false;
          (*m_cb)(m_str,m_pos,m_user_data);
     }
}

3.多个字符串的搜索

/**
 * 在不断追加的字符序列中，搜索多个字符串，成功匹配时调用指定的函数
 */
class msearcher
{
public:
     ///构造函数

     msearcher():m_searchers(){ }
     /**
      * 添加一个待搜索的子串
      *
      * @param substr 待匹配的字符串
      * @param cb 成功匹配时调用的回调函数
      * @param user_data 指向用户子定义的数据，这个数据会传递给回掉函数
      * @return 是否添加成功，如果有重复的子串会拒绝添加
      */
     void add_entry(const char *substr,
                         ok_callback_T cb,
                    void * user_data = NULL,
                    bool case_sentive = false);
     
     ///追加一个字符

     void feed(char more_ch);
     ///... ...

 private:
     std::vector<searcher*> m_searchers;

     ///禁止拷贝构造和赋值操作

     msearcher( const msearcher&);
     msearcher& operator=(const msearcher& );
     
};

完整的源代码包

文件:	searcher-1.0.tar.gz
大小:	162KB
下载:	下载

包中的源代码，除了包括上面的内容，还实现了一些方便searcher和msearcher使用的函数。另外，源代码中得到test_main.cpp包括两个测试用例：其中一对随机生成的字符串，进行搜索，并检查搜索结果。另外一个对一个文本文件中的常用单词和字母进行统计。

编译说明：
已经有了Makeifle文件，在searcher子路径下，直接运行make就可以编译。编译后生成的test，可以用来对算法进行测试。
已经测试的环境： gcc 4.2.3， GNU Make 3.81， debian linux