时间戳

首页 > 技术文章 > [经典算法] 字符串搜索Boyer-Moore

[经典算法] 字符串搜索Boyer-Moore

Quincy 2015-08-10 15:14 原文

题目说明：

今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、C#、Perl等），不过字串搜寻本身仍是个值得探讨的课题，在这边以Boyer- Moore法来说明如何进行字串说明，这个方法快且原理简洁易懂。

 

题目解析：

串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字串就不简单了，传统的字串搜寻是从关键字与字串的开头开始比对，例如 Knuth-Morris-Pratt 演算法 字串搜寻，这个方法也不错，不过要花时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然后比对字串中p-n+1至p的值是否与关键字相同。

如果关键字中有重复出现的字元，则前进值就会有两个以上的值，此时则取前进值较小的值，如此就不会跳过可能的位置，例如texture这个关键字，t的前 进值应该取后面的3而不是取前面的7。

 

程序代码：

#include<iostream>
#include<string.h>

using namespace std;

int SkipTbl[256];

void BuildSkipTable(char* input)
{
    int length = strlen(input);
    for (int i=0; i < 256; ++i)
    {
        SkipTbl[i] = length;
    }

    for (int i=0; i < length - 1; ++i)
    {
        SkipTbl[input[i]] = length - i - 1;
    }
}

int Search(int pos, char* input, char* key)
{
    int n = strlen(input);
    int m = strlen(key);

    while (pos < n)
    {
        if (memcmp(input+pos-m+1, key, m)==0)
        {
            return pos - m + 1;
        }

        pos += SkipTbl[input[pos]];
    }

    return -1;
}

int main()
{
    char input[100] = {0};
    char key[10] = {0};
    cin.getline(input, 100);
    cin.getline(key, 10);

    int m = strlen(key);
    BuildSkipTable(key);

    int pos = Search(m-1, input, key);
    while (-1 != pos)
    {
        cout << "Search, index=" << pos <<endl;
        pos = Search(pos+m+1, input, key);
    }

    return 0;
}

推荐阅读