字符串匹配 — Horspool

• 如果c不包含在模式的前m-1个字符中，则t(c) = 模式长度m
• t(c) = 模式前m-1个字符中最右边的c到模式最后一个字符的距离

#include <iostream>
#include <string>
#include <map>
#include <vector>
 
using namespace std;
 
void Get_Next(const string &text, const string &pattern, map<char, int> &next)
{
    int text_len = text.size();
    int pattern_len = pattern.size();
 
    for (int i = 0; i < text_len; i++)
        next.insert(make_pair(text[i], pattern_len));
 
    for (int i = 0; i < pattern_len - 1; i++)
        next[pattern[i]] = pattern_len - 1 - i;
}
 
void Horspool(const string &text, const string &pattern, vector<int> &result)
{
    int text_len = text.size();
    int pattern_len = pattern.size();
    map<char, int> next;    // 使用map容器记录移动表
 
    Get_Next(text, pattern, next);
 
    for (int i = pattern_len - 1; i < text_len; /* NULL */)
    {
        int text_pos = i;
        int pattern_pos;
        for (pattern_pos = pattern_len - 1; pattern_pos >= 0; /* NULL */)
        {
            if (text[text_pos] == pattern[pattern_pos])
            {
                text_pos--;
                pattern_pos--;
            }
            else
            {
                i += next[text[i]];   // i = 文本中对齐模式最后一个字符的位置
                break;
            }
        }
        if (pattern_pos <= 0)
        {
            result.push_back(i - pattern_len + 1);  // 完全匹配时的起始位置
            i++;
        }
    }
}
 
int main()
{
    string text = "hello world good google Nestle people google hello this is a test google";
    string pattern = "google";
    vector<int> result;
 
    Horspool(text, pattern, result);
 
    int cnt = 1;
    for (vector<int>::iterator iter = result.begin(); iter != result.end(); ++iter)
        cout << "match " << cnt++ << " = " << *iter << endl;
 
    system("pause");
    return 0;
}