WINX新增(1): KMP字符串查找算法

<iframe align="center" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>

概要

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流）中查找

voidtestSearchInArchive(LogT&log)
{
std::stringline;
std::StdioReadArchivear(__FILE__);

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

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

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

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

voidtestSearchInFStream(LogT&log)
{
std::stringline;
std::ifstreamis(__FILE__);

std::kmp::Finderchar>finder("std::ifstream");
HRESULThr=finder.istreamNext(is);
AssertExp(hr==S_OK);

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

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

voidtestSearchInCStr(LogT&log)
{
constchar*p;
constchardest[]="1234ababcde";

std::kmp::Finderchar>finder("abc");
HRESULThr=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）中查找

voidtestSearchInDeque(LogT&log)
{
typedefstd::dequechar>Container;

constchardestBuf[]="1234ababcde";
Container::iteratoritFind;
Containerdest(sizeof(destBuf));
std::copy(destBuf,destBuf+sizeof(destBuf),dest.begin());

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

附录

1. 完整的KMP字符串查找（匹配）算法的源代码，请参考这里：
   
   WINX之KMP字符串查找算法源码
   
2. 对WINX感兴趣？下载WINX开发包。
   
3. 本文对应英文版本是：KMP String Searching Algorithm in WINX。欢迎指出翻译不到位的地方（实在是硬着头皮上了）。
   
4. winx-1.1.02还加了哪些？更详细的内容参考这里。