概要
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流）中查找
{
std::string line;
std::StdioReadArchive ar(__FILE__);
std::kmp::Finder
char> finder("std::kmp::FinderHRESULT hr = finder.next(ar);
AssertExp(hr == S_OK);
ar.getline(line);
log.trace(
}
请问，这个函数执行输出什么？
2、在文件（C++标准流）中查找
{
std::string line;
std::ifstream is(__FILE__);
std::kmp::Finderchar> 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风格的字符串中查找
{
const char* p;
const char dest[] = "1234ababcde";
std::kmp::Finderchar> 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）中查找
{
typedef std::dequechar> 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);
}
附录
- 完整的KMP字符串查找（匹配）算法的源代码，请参考这里：
- 对WINX感兴趣？下载WINX开发包。
- 本文对应英文版本是：KMP String Searching Algorithm in WINX。欢迎指出翻译不到位的地方（实在是硬着头皮上了）。
- winx-1.1.02还加了哪些？更详细的内容参考这里。