KMP字符串查找算法

扫一扫
分享文章到微信
扫一扫
关注官方公众号
至顶头条

字符串匹配算法，输入有两个：一个是模式串（pattern），一个目标文本。

作者：许式伟来源：CSDN 2008年1月8日

概要

KMP字符串查找（匹配）算法，我相信多数人都已经了解了，这里不在赘述。我只是提几个关键点，然后讲一下WINX中的KMP字符串查找算法的用法。

字符串匹配算法，输入有两个：一个是模式串（pattern），一个目标文本。模式串比较小，通常std::string（或std::wstring就可以了）。而目标文本通常比较大，在多数实用的情形下，会是一个磁盘文本文件；或者内存中逻辑上的文本流，但实际上不是简单的字符串（不连续）。

KMP字符串查找（匹配）算法最大的好处，并不是它比strstr快，而是它不回溯。这是很奇妙的一个特征。这意味着目标文本只需要提供一个取得下一个字符的函数（在WINX中，这个函数叫get），就可以实现搜索。这对KMP算法的客户而言，无疑是非常有利的一件事情。

WINX的KMP字符串查找（匹配）算法总体来说用法很简单，唯一需要注意的是，和一般的匹配算法不同，WINX匹配成功后，目标文本中当前位置（position）指向的是被匹配串的末尾，而不是开始。例如，C库的strstr("1234abcdefg", "abc")，返回的结果是指向"abcdefg"中的'a'。而WINX的KMP算法返回的是"defg"中的'd'。

样例

我们这里给几个样例（这里假设以大小写敏感，如果要大小写不敏感，只需要换成把Finder类换成NoCaseFinder类）。

1、在文件（WINX的Archive流）中查找

    void testSearchInArchive(LogT& log)
    {
        std::string line;
        std::StdioReadArchive ar(__FILE__);

        std::kmp::Finder<char> finder("std::kmp::Finder<char>");
        HRESULT hr = finder.next(ar);
        AssertExp(hr == S_OK);

        ar.getline(line);
        log.trace(" line =%s ", line.c_str());
    }

请问，这个函数执行输出什么？

2、在文件（C++标准流）中查找

    void testSearchInFStream(LogT& log)
    {
        std::string line;
        std::ifstream is(__FILE__);

        std::kmp::Finder<char> finder("std::ifstream");
        HRESULT hr = finder.istreamNext(is);
        AssertExp(hr == S_OK);

        std::getline(is, line);
        log.trace(" line =%s ", line.c_str());
    }

3、在C风格的字符串中查找

    void testSearchInCStr(LogT& log)
    {
        const char* p;
        const char dest[] = "1234ababcde";

        std::kmp::Finder<char> finder("abc");
        HRESULT hr = finder.cstrNext(dest, &p);
        AssertExp(hr == S_OK);
        AssertExp(strcmp(p, "de") == 0);
    }

可以看到，finder.cstrNext返回p是指向"de"，而不是"abcde"。

要让它指向"abcde"，很简单，只需要执行:
p -= finder.size();

这里finder.size()返回的是模式串(pattern)的大小。

4、在STL的容器（如deque）中查找

    void testSearchInDeque(LogT& log)
    {
        typedef std::deque<char> Container;

        const char destBuf[] = "1234ababcde";
        Container::iterator itFind;
        Container dest(sizeof(destBuf));
        std::copy(destBuf, destBuf+sizeof(destBuf), dest.begin());

        std::kmp::Finder<char> finder("abc");
        HRESULT hr = finder.iteratorNext(dest.begin(), dest.size(), &itFind);
        AssertExp(hr == S_OK);
        AssertExp(dest.end() - itFind == 3);
    }

查看本文来源