字符串匹配的KMP算法 - 文章 - 伯乐在线
& 字符串匹配的KMP算法
是计算机的基本任务之一。
举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串”ABCDABD”？
许多算法可以完成这个任务，（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。
这种算法不太容易理解，网上有很多，但读起来都很费劲。直到读到的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。
首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
因为B与A不匹配，搜索词再往后移。
就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
接着比较字符串和搜索词的下一个字符，还是相同。
直到字符串有一个字符，与搜索词对应的字符不相同为止。
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。
怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。
已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数：
　　移动位数 = 已匹配的字符数 – 对应的部分匹配值
因为 6 – 2 等于4，所以将搜索词向后移动4位。
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 – 0，结果为 2，于是将搜索词向后移2位。
因为空格与A不匹配，继续后移一位。
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 – 2，继续将搜索词向后移动4位。
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 – 0，再将搜索词向后移动7位，这里就不再重复了。
下面介绍《部分匹配表》是如何产生的。
首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，
　　－　”A”的前缀和后缀都为空集，共有元素的长度为0；
－　”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
－　”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－　”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－　”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
－　”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
－　”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。
可能感兴趣的话题
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2016 伯乐在线博客访问： 992475
博文数量： 267
博客积分： 1305
博客等级： 军士长
技术积分： 4546
注册时间：
不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
& &KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n)；而KMP算法，可以证明它的时间复杂度为O(m+n)。
一、简单匹配算法
& &先来一个简单的匹配算法的函数。
int Index_BF(char const *S, char const *T, int pos)
&&&&/*--------------本人修改-------------*/
&&&&if(S&==&NULL&||&T&== NULL)
&&&&&&&&&return -1;
&&&&if(pos < 0 || pos > strlen(S) - strlen(T))
&&&&&&&&&return -1;
&&&&/*------------------------------------*/
&&&&//若串S中从第pos(S的下标0<= pos <=StrLength(S))个字符起存在和串T相同的子串，则匹配成功。
&&&&//返回第一个这样的子串在串S中的下标；否则返回-1
&&&&int i = pos;
&&&&int j = 0;
&&&&while(S[i+j]!='\0' && T[j] != '\0')
&&&&&&&&if(S[i+j] == T[j])
&&&&&&&&&&&&j++;//继续比较后一个字符
&&&&&&&&else
&&&&&&&&&&&&//重新开始新一轮的匹配
&&&&&&&&&&&&i++;
&&&&&&&&&&&&j=0;
&&&&if(T[j] == '\0')
&&&&&&&&return i;//匹配成功，返回下标
&&&&&&&&return -1;//串S中(第pos个字符起)不存在和串T相同的子串
& &此算法的思想是直截了当的：将主串S中某个位置i起始的子串与模式串T相比较。即从j=0起比较S[i+j]与T[j]，如相等，则在主串S中存在以i为起始位置匹配成功的可能性，继续往后比较(j逐步加1)，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的“匹配”，即将串T向后滑动一位，即i增1，而j退回到0，重新开始新一轮的匹配。
& &例如：在串S=“abcabcabdabba”中查找T=“abcabd”(我们可以假设从下标0开始)：先是比较S[0]和T[0]是否相等，然后比较S[1]和T[1]是否相等….我们发现一直比较到S[5]和T[5]才不等。如图所示。
&&&&当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1，然后再次比较。如下图所示。
&&&&这次立刻发生了失配，T下标又回溯到开始，S下标增1，然后再次比较。如图所示。
& &这次立刻发生了失配，T下标又回溯到了开始，S下标增1，然后再次比较。如图所示。
&&&&又一次发生了失配，所以T下标又回溯到了开始，S下标增1，然后再次比较。这次T中的所有字符和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图所示。
二、KMP算法
& &还是相同的例子，在S=“abcabcabdabba”中查找T=“abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5]和T[5]不等后，S下标不是回溯到1，T下标也不少回溯到开始，而是根据T中T[5]=’d’的模式函数值(next[5]=2，为什么？后面讲)，直接比较S[5]和T[2]是否相等，因为相等，S和T的下标同时增加；因为又相等，S和T的下标又同时增加…..最终在S中找到了T。如图所示。
& &KMP匹配算法和简单匹配算法效率比较，一个极端的例子是：
& &在S=“AAAAAA…AAB”(100个A)中查找T=“AAAAAAAAAB”，简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。如果使用KMP匹配算法，就不必回溯。
& &对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O (m+n)，因此在多数的实际应用场合下被应用。
& &KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子，为什么T[5] ==‘d’的模式函数值等于2(next[5]=2)，起始这个2表示T[5]==‘d’的前面有两个字符和开始的两个字符相同，且T[5]==’d’不等于开始的两个字符之后的第三个字符（T[2]=‘c’）。如图所示。
& &也就是说，如果开始的两个字符之后的第三个字符也为‘d’，那么，尽管T[5]==‘d’的前面有2个字符和开始的两个字符相同，T[5]==’d’的模式值也不为2，而是为0.
& &前面我说：在S=“abcabcabdabba”中查找T=“abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根 据T中T[5]==‘d’的模式函数值，直接比较S[5] 和T[2]是否相等。为什么可以这样？
& &刚才我又说：“（next[5]=2），其实这个2表示T[5]==‘d’的前面有2个字符和开始的两个字符相同”。请看图 ：因为，S[4] ==T[4]，S[3] ==T[3]，根据next[5]=2，有T[3]==T[0]，T[4] ==T[1]，所以S[3]==T[0]，S[4] ==T[1]（两对相当于间接比较过了），因此，接下来比较S[5] 和T[2]是否相等。
& &有人可能会问：S[3]和T[0]，S[4] 和T[1]是根据next[5]=2间接比较相等，那S[1]和T[0]，S[2] 和T[0]之间又是怎么跳过，可以不比较呢？因为S[0]=T[0]，S[1]=T[1]，S[2]=T[2]，而T[0] != T[1], T[1] != T[2],==> S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。
& &有人疑问又来了，你分析的是不是特殊轻况啊。
& &假设S不变，在S中搜索T=“abaabd”呢？
& &答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
& &假设S不变，在S中搜索T=“abbabd”呢？
& &答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。
& &假设S=“abaabcabdabba”在S中搜索T=“abaabd”呢？
& &答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
& &总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、模式函数值、模式值是一个意思。）
三、怎么求串的模式值next[]
& &(1) next[0] = -1
& &意义：任何串的第一个字符的模式值规定为-1。
& &(2) next[j] = -1
& &意义：模式串T中的下标为j的字符，如果与首字符相同，且j的前面的1-k个字符与开头的1-k个字符不等（或者相等但T[k]==T[j]，1<=k<j）
& &(3) next = k
& &意义：模式串T中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] !=T[k]，1<=k<j。
& &(4) next[j] = 0
& &意义：除（1）、（2）、（3）的其他情况。
& &01）求T=“abcac”的模式函数的值
&&&& next[0] = -1 根据（1）
&&&&next[1] = 0 根据（4） 因（3）有1<=k<j；不能说，j=1，T[j-1]==T[0]
&&&&next[2] = 0 根据（4） 因（3）有1<=k<j；（T[0]=a）!= （T[1]=b）
&&&&next[3] =-1 根据（2）&
&&&& next[4] = 1 根据(3) T[0]=T[3] 且 T[1]=T[4]
&&&&为什么T[0] == T[3]，还会有next[4] = 0呢？因为T[1]==T[4]，根据（3）且T[j]!=T[k]被划入（4）。
&&&&02）来点复杂点的，求T=“ababcaabc”的模式函数的值。
&&&&next[0] = -1 根据（1）
&&&&next[1] = 0 根据（4）
&&&&next[2] = -1 根据（2）
&&&&next[3] = 0 根据（3）虽T[0]=T[2] 但T[1]=T[3]被划入了（4）
&&&&next[4] = 2 根据（3）T[0]T[1]=T[2]T[3] 且T[2]!=T[4]
&&&&next[5] = -1 根据（2）
&&&&next[6] = 1 根据（3）T[0]=T[5] 且T[1]!=T[6]
&&&&next[7] = 0 根据（3）虽T[0]=T[6] 但T[1]=T[7]被划入（4）
&&&&next[8] = 2 根据（3）T[0]T[1]=T[6]T[7] 且T[2]!=T[8]
& &只要理解了next[3]=0，而不是=1，next[6] =1，而不是=-1，next[8]=2，而不是=0，其他的好像都容易理解。
& &03）来个特殊的，求T=“abCabCad”的模式函数的值。
&&&&&next[5] = 0 根据（3） 虽T[0]T[1]=T[3]T[4]，但T[2]=T[5]
&&&&next[6] = -1 根据（2） 虽前面有abC=abC，但T[3]==T[6]
&&&&next[7] = 4 根据（3）&前面有abCa=abCa，且T[4]!=T[7]
& &04）若T[4]==T[7]，即T=” adCadCad”,那么将是这样：next[7]=0, 而不是= 4,因为T[4]==T[7]。
& &如果你觉得你懂了，那么，进行一个小的练习。
练习：求T=”AAAAAAAAAAB”的模式函数值，并用后面的求模式函数值函数验证。
& &next函数值究竟有什么含义呢？前面说过一些，这里总结：
& &设在字符串S中查找模式串T，若S[m]!=T[n]，那么，取T[n]的模式函数next[n],
& &(1) next[n] = -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较S[m+1]和T[0]
& &(2) next[0] = 0 &表示比较过程中产生了不相等，下一次比较S[m]和T[0]
& &(3) next[n] = k>0 && k<n 表示S[m]的前k个字符与T中的开始的k个字符已经间接的比较相等了，下一次比较S[m]和T[k]相等吗？
& &(4) 其他值，不可能。
四、KMP算法的实现
/*如果有什么问题，请多多指出，会虚心学习的*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*功能：求模式串值
&*参数：ptn：模式串
&*nextval：保存模式串值的数组
void get_nextval(char const *ptn, int *nextval)
&&&&int i = 0;
&&&&nextval[0] = -1;
&&&&int j = -1;
&&&&int plen = strlen(ptn);
&&&&if(ptn == NULL || nextval == NULL)
&&&&&&&&return;
&&&&while(i < plen)
&&&&&&&&if(j == -1 || ptn[i] == ptn[j])
&&&&&&&&&&&&++i;
&&&&&&&&&&&&++j;
&&&&&&&&&&&&if(ptn[i] != ptn[j])
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&nextval[i] = j;
&&&&&&&&&&&&}
&&&&&&&&&&&&else
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&nextval[i] = nextval[j];
&&&&&&&&&&&&}
&&&&&&&&else
&&&&&&&&&&&&j = nextval[j];
/*功能：实现KMP算法
&*参数：src：源串
&* & & &patn：模式串
&* & & &nextval：模式串值
&* & & &pos：源串开始的位置
&*返回值：若匹配成功，则返回下标；若出错或匹配不成功，则返回-1
int kmp_search( char const *src, char const *patn, int const *nextval,int pos)
&&&&int i = pos;
&&&&int j = 0;
&&&&if(src == NULL || patn ==NULL)
&&&&&&&&return -1;
&&&&int slen = strlen(src);
&&&&int plen = strlen(patn);
&&&&if(pos < 0 || pos > slen)
&&&&&&&&return -1;
&&&&while(i < slen && j < plen)
&&&&&&&&if(j == -1 || src[i] == patn[j])
&&&&&&&&&&&&++i;
&&&&&&&&&&&&++j;
&&&&&&&&else
&&&&&&&&&&&&j = nextval[j];
&&&&&&&&&&&&//当匹配失效时，直接用p[j_next]与s[i]比较
&&&&&&&&&&&&//下面阐述怎么求这个值，即匹配失效后的下一次匹配的位置
&&&&if( j >= plen)
&&&&&&&&return i - plen;//返回下标，从0开始
&&&&&&&&return -1;
int main()
&&&&char src[] = "aabcabcebafabcabceabcaefabcacdabcababce";
&&&&char prn[] = "abce";
&&&&int *nextval = (int *)malloc(sizeof(int)* strlen(prn));
&&&&get_nextval(prn,nextval);
&&&&int i =0;
&&&&for(i = 0; i < strlen(prn); i++)
&&&&&&&&printf("%d ",nextval[i]);
&&&&printf("\n");
&&&&printf("the result is : %d\n",kmp_search(src, prn, nextval,5));
&&&&return 0;
& &KMP的时间复杂度为O(n + m)，空间复杂度为O(m)。
& &简单字符串匹配算法的时间复杂度为O(n*m)，空间复杂度为O(1)。
& &其中，n为原串的长度，m为模式串的长度。
& &先前看关于字符串匹配的相关算法，KMP算法肯定是不能落下的，知道模式串next[]数组比较难理解，所以，从网上、书上查找资料，发现了几篇讲述next[]和KMP算法非常容易理解的文章，再加上自己的罗嗦和修改，才有了下面的文字，记录下来，仅仅是为了自己以后回头看的方便，别无它意，如果能为他人带来参考，那样更好。我无意侵犯前辈的权益，如果您们感觉有所侵犯，请及时通知，我会删除相应文字。
& &再次对您们的贡献表示感谢！
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & &梦醒潇湘
& & && && && 16:06
阅读(9330) | 评论(0) | 转发(2) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。从键盘输入两个字符串,查找第二个字符串在第一个字符串中出现的次数_百度知道
从键盘输入两个字符串,查找第二个字符串在第一个字符串中出现的次数
请用自定义函数实现，例子中出现的次数是一次
则输出1？。能给我完整的程序代码吗，查找从键盘输入的第二个字符串“ab”在第一个字符串中出现的次数例如
从键盘输入第一个字符串“abcdefg”
提问者采纳
.....字符串匹配问题 经典算法有kmp和Sunday.
用c语言编程实现
我要现代码。你写出来我就采纳你的。
int SUNDAY(char *text, char *patt){
register size_t temp[256];
size_t *shift =
size_t i, patt_size = strlen(patt), text_size = strlen(text);
&#47;&#47;cout && &size : & && patt_size &&
for( i=0; i & 256; i++ ) {
*(shift+i) = patt_size+1; }
for( i=0; i & patt_ i++ ) {
char(*(patt+i))) = patt_size-i; } size_t limit = text_size - patt_size+1;
for(i=0; i & i += shift[ text[i+patt_size] ]) {
if( text[i] == *patt )
char *match_text = text + i + 1;
size_t match_size = 1;
if( match_size == patt_size )
&#47;&#47;printf(&%d &,i);
}while((*match_text++) == patt[match_size++]);
不过我要的是用c语言编写的代码。需要的只是简单的自定义函数加主函数实现。你写这个我看不懂 啊，麻烦了
不能运行么............上面是自定义函数部分的内容
是不能运行诶
#include &iostream&#include &string&int ans = 0;int main(void){
char *text = new char[];
cin.getline(text,,&#39;&#92;n&#39;); char *patt = new char[];
cin.getline(patt,,&#39;&#92;n&#39;);printf(&%d&, SUNDAY(text,patt)); system(&pause&); return 0; } 你把上一段复制在空白那块连起来试试看....
提问者评价
虽然还是不行 不过谢谢你了
其他类似问题
为您推荐：
键盘输入的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁笨办法学C 练习39：字符串算法 - 简书
下载简书移动应用
写了270901字，被180人关注，获得了303个喜欢
笨办法学C 练习39：字符串算法
练习39：字符串算法
这个练习中，我会向你展示可能是最快的字符串搜索算法之一，并且将它与bstrlib.c中现有的binstr比较。binstr的文档说它仅仅使用了“暴力搜索”的字符串算法来寻找第一个实例。我所实现的函数使用Boyer-Moore-Horspool（BMH）算法，如果你分析理论时间的话，一般认为它会更快。你也会看到，如果我的实现没有任何缺陷，BMH的实际时间会比binstr简单的暴力搜索更糟。
这个练习的要点并不是真正解释算法本身，因为你可以直接去去阅读它。这个算法的要点就是它会计算出“跳跃字符列表”作为第一步操作，之后它使用这个列表来快速扫描整个字符串。它应当比暴力搜索更快，所以让我们在文件里写出代码来看看吧。
首先，创建头文件：
#ifndef string_algos_h
#define string_algos_h
#include &lcthw/bstrlib.h&
#include &lcthw/darray.h&
typedef struct StringScanner {
const unsigned char *
const unsigned char *
size_t skip_chars[UCHAR_MAX + 1];
int String_find(bstring in, bstring what);
StringScanner *StringScanner_create(bstring in);
int StringScanner_scan(StringScanner *scan, bstring tofind);
void StringScanner_destroy(StringScanner *scan);
为了观察“跳跃字符列表”的效果，我打算创建这个算法的两种版本：
String_find
只是在一个字符串中，寻找另一个字符串的首个实例，以一个动作执行整个算法。
StringScanner_scan
使用StringScanner状态结构，将跳跃列表的构建和实际的查找操作分开。这让我能看到什么影响了性能。这个模型有另一个优点，就是我可以在一个字符串中逐步搜索，并且快速地找到所有实例。
一旦你完成了头文件，下面就是实现了：
#include &lcthw/string_algos.h&
#include &limits.h&
static inline void String_setup_skip_chars(
size_t *skip_chars,
const unsigned char *needle, ssize_t nlen)
size_t i = 0;
size_t last = nlen - 1;
for(i = 0; i & UCHAR_MAX + 1; i++) {
skip_chars[i] =
for (i = 0; i & i++) {
skip_chars[needle[i]] = last -
static inline const unsigned char *String_base_search(
const unsigned char *haystack, ssize_t hlen,
const unsigned char *needle, ssize_t nlen,
size_t *skip_chars)
size_t i = 0;
size_t last = nlen - 1;
assert(haystack != NULL && "Given bad haystack to search.");
assert(needle != NULL && "Given bad needle to search for.");
check(nlen & 0, "nlen can't be &= 0");
check(hlen & 0, "hlen can't be &= 0");
while (hlen &= nlen)
for (i = haystack[i] == needle[i]; i--) {
if (i == 0) {
hlen -= skip_chars[haystack[last]];
haystack += skip_chars[haystack[last]];
error: // fallthrough
return NULL;
int String_find(bstring in, bstring what)
const unsigned char *found = NULL;
const unsigned char *haystack = (const unsigned char *)bdata(in);
ssize_t hlen = blength(in);
const unsigned char *needle = (const unsigned char *)bdata(what);
ssize_t nlen = blength(what);
size_t skip_chars[UCHAR_MAX + 1] = {0};
String_setup_skip_chars(skip_chars, needle, nlen);
found = String_base_search(haystack, hlen, needle, nlen, skip_chars);
return found != NULL ? found - haystack : -1;
StringScanner *StringScanner_create(bstring in)
StringScanner *scan = calloc(1, sizeof(StringScanner));
check_mem(scan);
scan-&in =
scan-&haystack = (const unsigned char *)bdata(in);
scan-&hlen = blength(in);
assert(scan != NULL && "fuck");
free(scan);
return NULL;
static inline void StringScanner_set_needle(StringScanner *scan, bstring tofind)
scan-&needle = (const unsigned char *)bdata(tofind);
scan-&nlen = blength(tofind);
String_setup_skip_chars(scan-&skip_chars, scan-&needle, scan-&nlen);
static inline void StringScanner_reset(StringScanner *scan)
scan-&haystack = (const unsigned char *)bdata(scan-&in);
scan-&hlen = blength(scan-&in);
int StringScanner_scan(StringScanner *scan, bstring tofind)
const unsigned char *found = NULL;
ssize_t found_at = 0;
if(scan-&hlen &= 0) {
StringScanner_reset(scan);
return -1;
if((const unsigned char *)bdata(tofind) != scan-&needle) {
StringScanner_set_needle(scan, tofind);
found = String_base_search(
scan-&haystack, scan-&hlen,
scan-&needle, scan-&nlen,
scan-&skip_chars);
if(found) {
found_at = found - (const unsigned char *)bdata(scan-&in);
scan-&haystack = found + scan-&
scan-&hlen -= found_at - scan-&
// done, reset the setup
StringScanner_reset(scan);
found_at = -1;
return found_
void StringScanner_destroy(StringScanner *scan)
if(scan) {
free(scan);
整个算法都在两个static inline的函数中，叫做String_setup_skip_chars 和 String_base_search。它们在别的函数中使用，用于实现我想要的的搜索形式。研究这两个函数，并且与维基百科的描述对比，你就可以知道它的工作原理。
之后String_find使用这两个函数来寻找并返回所发现的位置。它非常简单并且我使用它来查看“跳跃字符列表”的构建如何影响到真实性能。要注意，你或许可以使它更快，但是我要教给你在你实现算法之后如何验证理论速度。
StringScanner_scan函数随后按照“创建、扫描、销毁”的常用模式，并且用于在一个字符串中逐步搜索另一个字符串。当我向你展示单元测试的时候，你会看到它如何使用。
最后，我编写了单元测试来确保算法有效，之后在它的注释部分，我为三个搜索函数运行了简单的性能测试：
#include "minunit.h"
#include &lcthw/string_algos.h&
#include &lcthw/bstrlib.h&
#include &time.h&
struct tagbstring IN_STR = bsStatic("I have ALPHA beta ALPHA and oranges ALPHA");
struct tagbstring ALPHA = bsStatic("ALPHA");
const int TEST_TIME = 1;
char *test_find_and_scan()
StringScanner *scan = StringScanner_create(&IN_STR);
mu_assert(scan != NULL, "Failed to make the scanner.");
int find_i = String_find(&IN_STR, &ALPHA);
mu_assert(find_i & 0, "Failed to find 'ALPHA' in test string.");
int scan_i = StringScanner_scan(scan, &ALPHA);
mu_assert(scan_i & 0, "Failed to find 'ALPHA' with scan.");
mu_assert(scan_i == find_i, "find and scan don't match");
scan_i = StringScanner_scan(scan, &ALPHA);
mu_assert(scan_i & find_i, "should find another ALPHA after the first");
scan_i = StringScanner_scan(scan, &ALPHA);
mu_assert(scan_i & find_i, "should find another ALPHA after the first");
mu_assert(StringScanner_scan(scan, &ALPHA) == -1, "shouldn't find it");
StringScanner_destroy(scan);
return NULL;
char *test_binstr_performance()
int i = 0;
int found_at = 0;
unsigned long find_count = 0;
time_t elapsed = 0;
time_t start = time(NULL);
for(i = 0; i & 1000; i++) {
found_at = binstr(&IN_STR, 0, &ALPHA);
mu_assert(found_at != BSTR_ERR, "Failed to find!");
find_count++;
elapsed = time(NULL) -
} while(elapsed &= TEST_TIME);
debug("BINSTR COUNT: %lu, END TIME: %d, OPS: %f",
find_count, (int)elapsed, (double)find_count / elapsed);
return NULL;
char *test_find_performance()
int i = 0;
int found_at = 0;
unsigned long find_count = 0;
time_t elapsed = 0;
time_t start = time(NULL);
for(i = 0; i & 1000; i++) {
found_at = String_find(&IN_STR, &ALPHA);
find_count++;
elapsed = time(NULL) -
} while(elapsed &= TEST_TIME);
debug("FIND COUNT: %lu, END TIME: %d, OPS: %f",
find_count, (int)elapsed, (double)find_count / elapsed);
return NULL;
char *test_scan_performance()
int i = 0;
int found_at = 0;
unsigned long find_count = 0;
time_t elapsed = 0;
StringScanner *scan = StringScanner_create(&IN_STR);
time_t start = time(NULL);
for(i = 0; i & 1000; i++) {
found_at = 0;
found_at = StringScanner_scan(scan, &ALPHA);
find_count++;
} while(found_at != -1);
elapsed = time(NULL) -
} while(elapsed &= TEST_TIME);
debug("SCAN COUNT: %lu, END TIME: %d, OPS: %f",
find_count, (int)elapsed, (double)find_count / elapsed);
StringScanner_destroy(scan);
return NULL;
char *all_tests()
mu_suite_start();
mu_run_test(test_find_and_scan);
// this is an idiom for commenting out sections of code
mu_run_test(test_scan_performance);
mu_run_test(test_find_performance);
mu_run_test(test_binstr_performance);
return NULL;
RUN_TESTS(all_tests);
我把它们写在#if 0中间，它是使用C预处理器来注释一段代码的方法。像这样输入，并且把它和#endif移除，你就可以运行性能测试。当你继续这本书时，需要简单地把它们再次注释，以防它们浪费你的开发时间。
这个单元测试没有什么神奇之处，它只是在尊换种调用每个不同的函数，循环需要持续足够长的时间来得到一个几秒的样本。第一个测试（test_find_and_scan）只是确保我所编写的代码正常工作，因为测试无效的代码没有意义。之后，下面的三个函数使用三个函数中的每一个来执行大量的搜索。
需要注意的一个技巧是，我在start中存储了起始时间，之后一直循环到至少过了TEST_TIME秒。这确保了我能或得到足够好的样本用于比较三者。我之后会使用不同的TEST_TIME设置来运行测试，并且分析结果。
你会看到什么
当我在我的笔记本上运行测试时，我得到的数据是这样的：
$ ./tests/string_algos_tests
DEBUG tests/string_algos_tests.c:124: ----- RUNNING: ./tests/string_algos_tests
RUNNING: ./tests/string_algos_tests
DEBUG tests/string_algos_tests.c:116:
----- test_find_and_scan
DEBUG tests/string_algos_tests.c:117:
----- test_scan_performance
DEBUG tests/string_algos_tests.c:105: SCAN COUNT: , END TIME: 2, OPS: 000
DEBUG tests/string_algos_tests.c:118:
----- test_find_performance
DEBUG tests/string_algos_tests.c:76: FIND COUNT: , END TIME: 2, OPS: 000
DEBUG tests/string_algos_tests.c:119:
----- test_binstr_performance
DEBUG tests/string_algos_tests.c:54: BINSTR COUNT: , END TIME: 2, OPS: 000
ALL TESTS PASSED
Tests run: 4
我看到了它，觉得每轮运行应该超过两秒。并且，我打算多次运行它，并且像之前一样使用R来验证。下面是我获得的10个样例，每个基本上是10秒：
scan find binstr
我在shell的一点点帮助下获取数据，之后编辑输出：
$ for i in 1 2 3 4 5 6 7 8 9 10; do echo "RUN --- $i" && times. ./tests/string_algos_tests 2&&1 | grep COUNT && times. done
$ less times.log
$ vim times.log
现在你可以看到scan系统要优于另外两个，但是我会在R中打开它并且验证结果：
& times &- read.table("times.log", header=T)
& summary(times)
1st Qu.:6358100
Median :6374750
3rd Qu.:6447100
为了理解我为什么要生成这份概要统计，我必须对你解释一些统计学概念。我在这些数字中寻找的东西能够简单地告诉我，“这三个函数（scan、find、binstr）实际上不同吗？”我知道每次我运行测试函数的时候，我都会得到有些不同的数值，并且那些数值始终处理一个固定的范围。你可以看到两个四分位数反映了这一点。
我首先会去看均值，并且我会观察每个样例的均值是否不同于其它的。我可以清楚地看到scan优于binstr，同时后者优于find。然而问题来了，如果我只使用均值，就可以出现每个样例的范围会重叠的可能性。
如果均值不同，但是两个四分位点重叠会怎么用？这种情况下我只能说有这种可能性，并且如果我再次运行测试，均值就可能不同了。很可能出现的范围上的重叠是，我的两个样例（以及两个函数）并非实际上不同。任何我看到的差异都是随机产生的结果。
统计学拥有大量工具来解决这一问题，但是在我们的例子中我可以仅仅观察两个四分位值，以及所有样例的均值。如果均值不同，并且四分位值不可能重叠，就可以说它们完全不同。
在我的三个样例中，我可以说scan、find和binstr都是不同的，范围上没有重叠，并且（最重要的是）我可以相信数据。
从结果中可以看出String_find比其它两个更慢。实际上，我认为慢的原因是我实现的方式有些问题。然而当我将它与StringScanner_scan比较时，我发现正是构造跳跃列表的那一部分最消耗时间。并且它的功能比scan要少，因为它仅仅找到了第一个位置，而scan找到了全部。
我也可以发现scan以很大优势优于binstr。同时我可以说scan的功能比其他两个要多，速度也更快。
下面是这个分析的一些注解：
我可能将实现或测试弄乱了。现在我打算研究所有实现BMH的可能方式来改进它。我也会确保我所做的事情正确。
如果你修改了测试运行的时间，你会得到不同的结果。这就是我没有考虑的”热身“环节。
test_scan_performance单元测试和其它两个并不相同，但是它比其它测试做得更多（并且也是按照时间和操作数量计算的），所以他可能是合理的。
我只通过在一个字符串内搜索另一个来执行测试。我应该使所查找的字符串随机化，来移除它们的位置和长度，作为干扰因素。
binstr的实现可能比“暴力搜索”要好。（所以应该自己编写暴力搜索作为对照。）
我可能以不幸的顺序来执行这些函数，并且随机化首先运行的测试可能会得到更好的结果。
可以从中学到的是，你需要确保知己的性能，即使你“正确”实现了一个算法。在这里BMH算法应该优于binstr算法，但是一个简单的测试证明了它是错误。如果我没有这些测试，我可能就使用了一个劣等的算法实现而不自知。参照这些度量，我可以开始调优我的实现，或者只是抛弃它并寻找新的算法。
看看你能不能使Scan_find更快。为什么我的实现这么慢？
尝试一些不同的搜索时长，看看你是否能得到不同的数值。当你改变scan的测试时间时，时间的长度会有什么影响？对于这些结果你能得出什么结论？
修改单元测试，使它最开始执行每个函数一小段时间，来消除任何“热身”缓解。这样会修改所运行时长的依赖性吗？每秒可能出现多少次操作？
使单元测试中的所查找字符串随机化，之后测量你的得到的性能。一种实现它的方式就是使用bstrlib.h中的bsplit函数在空格处分割IN_STR。之后使用你得到的strList结构访问它返回的每个字符串。这也教给你如何使用bstrList操作进行字符串处理。
尝试一些不同顺序的测试，看看能否得到不同的结果。
喜欢我的文章的话，点下面的喜欢就好了。除了催更之外不要打赏，打赏是要钱的。
打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
被以下专题收入，发现更多相似内容：
如果你是程序员，或者有一颗喜欢写程序的心，喜欢分享技术干货、项目经验、程序员日常囧事等等，欢迎投稿《程序员》专题。
投稿须知：
...
· 135684人关注
Github：/wizardforcel/lcthw-zh
· 21人关注
喜欢我的文章的话，点下面的喜欢就好了。除了催更之外不要打赏，打赏是要钱的。
选择支付方式：}