BM模式匹配算法图解
Boyer-Moore 经典单模式匹配算法
BM模式匹配算法-原理（图解）
由于毕业设计（入侵检测）的需要，这两天仔细研究了BM模式匹配算法，稍有心得，特此记下。
首先，先简单说明一下有关BM算法的一些基本概念。
BM算法是一种精确字符串匹配算法（区别于模糊匹配）。
BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。
BM算法的基本流程: 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，如下图所示:
若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。
下面，来详细介绍一下坏字符规则和好后缀规则。
首先，诠释一下坏字符和好后缀的概念。
请看下图：
图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。
1）坏字符规则（Bad Character）：
在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：
i. 如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。
ii. 如果x在模式P中出现且出现次数>=1，则以该字符所在最右边位置进行对齐。
用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。
可以总结为字符x出现与否，将max(x)=0作为初值即可。
例1：
下图红色部分，发生了一次不匹配。
计算移动距离Skip(c) = m-max(c)=5 - 3 = 2，则P向右移动2位。
移动后如下图：
2）好后缀规则（Good Suffix）：
若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：
i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。
ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。
用数学公式表示，设Shift(j)为P右移的距离，m为模式串P的长度，j 为当前所匹配的字符位置，s为t'与t的距离（以上情况i）或者x与P''的距离（以上情况ii）。
以上过程有点抽象，所以我们继续图解。
例2：
下图中，已匹配部分cab（绿色）在P中再没出现。
再看下图，其后缀T'（蓝色）与P中前缀P'（红色）匹配，则将P'移动到T'的位置。
移动后如下图：
自此，两个规则讲解完毕。
在BM算法匹配的过程中，取SKip(x)与Shift(j)中的较大者作为跳跃的距离。
BM算法预处理时间复杂度为O（m+s），空间复杂度为O(s)，s是与P, T 相关的有限字符集长度，搜索阶段时间复杂度为O(m·n)。
最好情况下的时间复杂度为O(n/m)，最坏情况下时间复杂度为O(m·n)。BM模式匹配算法-实现（C语言）
下面是SNORT2.7.0中提取出的代码。
1./*
2.函数：int* MakeSkip(char *, int)
3.目的：根据坏字符规则做预处理，建立一张坏字符表
4.参数：
5. ptrn => 模式串P
6. PLen => 模式串P长度
7.返回：
8. int* - 坏字符表
9.*/
10.int* MakeSkip(char *ptrn, int pLen)
11.{
12. int i;
13. //为建立坏字符表，申请256个int的空间
14. /*PS:之所以要申请256个，是因为一个字符是8位，
15. 所以字符可能有2的8次方即256种不同情况*/
16. int *skip = (int*)malloc(256*sizeof(int));
17.
18. if(skip == NULL)
19. {
20. fprintf(stderr, "malloc failed!");
21. return 0;
22. }
23.
24. //初始化坏字符表，256个单元全部初始化为pLen
25. for(i = 0; i < 256; i++)
26. {
27. *(skip+i) = pLen;
28. }
29.
30. //给表中需要赋值的单元赋值，不在模式串中出现的字符就不用再赋
值了
31. while(pLen != 0)
32. {
33. *(skip+(unsigned char)*ptrn++) = pLen--;
34. }
35.
36. return skip;
37.}
38.
39.
40./*
41. 函数：int* MakeShift(char *, int)
42. 目的：根据好后缀规则做预处理，建立一张好后缀表
43. 参数：
44. ptrn => 模式串P
45. PLen => 模式串P长度
46. 返回：
47. int* - 好后缀表
48.*/
49.int* MakeShift(char* ptrn,int pLen)
50.{
51. //为好后缀表申请pLen个int的空间
52. int *shift = (int*)malloc(pLen*sizeof(int));
53. int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指
标
54. char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指
标
55. char c;
56.
57. if(shift == NULL)
58. {
59. fprintf(stderr,"malloc failed!");
60. return 0;
61. }
62.
63. c = *(ptrn + pLen - 1);//保存模式串中最后一个字符，因为要反
复用到它
64.
65. *sptr = 1;//以最后一个字符为边界时，确定移动1的距离
66.
67. pptr--;//边界移动到倒数第二个字符（这句是我自己加上去的，因
为我总觉得不加上去会有BUG，大家试试“abcdd”的情况，即末尾两位重复的情况）
68.
69. while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个
单元进行赋值的工作
70. {
71. char *p1 = ptrn + pLen - 2, *p2,*p3;
72.
73. //该do...while循环完成以当前pptr所指的字符为边界时，要
移动的距离
74. do{
75. while(p1 >= ptrn && *p1-- != c);//该空循环，寻找与最
后一个字符c匹配的字符所指向的位置
76.
77. p2 = ptrn + pLen - 2;
78. p3 = p1;
79.
80. while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);/
/该空循环，判断在边界内字符匹配到了什么位置
81.
82. }while(p3 >= ptrn && p2 >= pptr);
83.
84. *sptr = shift + pLen - sptr + p2 - p3;//保存好后缀表中，
以pptr所在字符为边界时，要移动的位置
85. /*
86. PS:在这里我要声明一句，
*sptr = （shift + pLen - sptr） + p2 - p3;
87. 大家看被我用括号括起来的部分，如果只需要计算字符串
移动的距离，那么括号中的那部分是不需要的。
88. 因为在字符串自左向右做匹配的时候，指标是一直向左移
的，这里*sptr保存的内容，实际是指标要移动
89. 距离，而不是字符串移动的距离。我想SNORT是出于性能
上的考虑，才这么做的。
90. */
91.
92. pptr--;//边界继续向前移动
93. }
94.
95. return shift;
96.}
97.
98.
99./*
100.函数：
int* BMSearch(char *, int , char *, int, int *, int *)
101.目的：判断文本串T中是否包含模式串P
102.参数：
103. buf => 文本串T
104. blen => 文本串T长度
105. ptrn => 模式串P
106. PLen => 模式串P长度
107. skip => 坏字符表
108. shift => 好后缀表
109.返回：
110. int - 1表示成功（文本串包含模式串），0表示失败（文本串不包含模式串）。
111.*/
112.int BMSearch(char *buf, int blen, char *ptrn, int plen, in t *skip, int *shift)
113.{
114.int b_idx = plen;
115. if (plen == 0)
116. return 1;
117. while (b_idx <= blen)//计算字符串是否匹配到了尽头118. {
119.int p_idx = plen, skip_stride, shift_stride; 120. while (buf[--b_idx] == ptrn[--p_idx])//开始匹配121. {
122. if (b_idx < 0)
123. return 0;
124. if (p_idx == 0)
125. {
126. return 1;
127. }
128. }
129. skip_stride = skip[(unsigned char)buf[b_idx]];//根据坏字符规则计算跳跃的距离
130. shift_stride = shift[p_idx];//根据好后缀规则计算跳跃的距离
131. b_idx += (skip_stride > shift_stride) ? skip_strid
e : shift_stride;//取大者
132. }
133. return 0;
134.}
经典单模式匹配算法：KMP、BM；经典多模式匹配算法：AC、Wu-Manber。貌似实用中，KMP跟C库strstr()效率相当，而BM能快上3x-5x。于是小女不才花了小天的功夫来研究这个BM算法。BM如何快速匹配模式？它怎么跳跃地？我今儿一定要把大家伙儿讲明白了，讲不明白您佬跟帖，我买单，包教包会。
模式，记为pat，用j作为索引; 文本，记为string（或text），用i作为索引。
Input: pat, string
Algorithm: BM，在string中进行pat匹配。
Output: 匹配上则返回匹配地址，否则返回-1。
图1
图1是一简单示意图。左对齐pat与string，小指针（记为p）指向对齐后的右end，开始比对。如果pat[p]= string[p]，那么小指针往左挪（挪到左end 说明匹配上了），否则就要滑动pat进行重新对齐，重新对齐后，小指针当然也要跟着溜到末位进行重新比对。那么究竟怎么个滑法？分四个case：
1.末位不匹配，且string[p]在pat中不存在，那么pat可以一下子右移patlen
个单位。因为你一个一个右移只是徒劳，没人跟string[i]能匹配上。比如，图1中F与T不匹配，且F在pat中不存在，那么我们可以把pat右滑patlen，小指针也跟着移至末位，移动后如图2所示。
图2
2.末位不匹配，但string[p]在pat中存在（如果有多个，那就找最靠右的
那个），距离pat右端为delta1。那么右移pat使得它们对齐。比如，图2中减号与T不匹配，但减号存在于pat中，数数知道delta1=4，那就右移pat使得两个减号对上，移动后如图3所示。
图3
总结：从1、2可以得到，
dealta1 = patlen, 当string[p]在patlen中不存在
= patlen –最右边那个string[p]的位置，当string[p]在patlen中存在delta1()是所有字符的函数，例如pat和string对应26个字母，那么dealta1(…a?)…dealta1(…z?)。只需扫描一下pat，就能记录下值了。别地儿管这个叫“坏字符规则”。
3.末m位都匹配上了(m m (m=4)位匹配上了，小指针指向的两个字符都发生了mismatch，记为mismatched char。 1)图4中示例1，string中的c在pat中的最右出现居然还在小指针靠 后的位置，总不至于为了让string中c跟pat中最右c匹配上就把pat 往回倒滑一个位置吧，才不要那么瓜，遇到这种情况就让pat往右滑 k=1个位置好了，此时小指针为了滑至最后需要滑k+m=5个位置。 2)图4中示例2，string中c在pat中的最右出现在小指针前面，那好 吧，就让此a跟彼a对齐吧。即让pat向右滑k=delta1(…a?)-m=6-4=2 个位置，此时小指针为了滑至最后需要滑 k+m={dealta1(…a?)-m}+m=dealta1(…a?)=6个位置。 3)图4中示例3，string中y在pat中未出现。那么将patlen向右移 k=delta1(…y?)-m=6-4=2个位置，此时小指针为了滑至最后需要滑 dealta1(…y?)=6个位置。 图4 总结：从3可以得到， pat右移位数= 1，当示例1 = k =delta1(…char?)-m，当示例2、3。. String右移位数= k+m 4.照着3那么移挺对也挺好地，但某些情况下，如图7的情况，能不能让 pat右移地更快呢？图7示例1，按3的分析只能将pat右滑1位，实际上我们可以放心右滑pat成示例2的样子，然后再将小指针移至末位开始匹配。 图7 下面的部分会比较绕，请读者用心看。图7示例1，末m(m=3)位即abc 匹配上了，记为subpat，那么pat中出现的最右abc且不由mismatched char 引导的位置，记为末subpat的“重现位置”，如”g abc f abc e abc e abc”重现位置应该是f引导的subpat，可以理解么？因为g引导的subpat不是最右的，倒数第2个e引导的subpat是由mismatched char引导的。 于是我们引入delta2(j)函数，j是发生mismatched的位置，我们记subpat 的“重现位置”为rpr(j)，那么pat应该右移k，相应地string右移k+m。如何计算k? 预处理pat，j=1…patlen，那么rpr(j)是指以j为mismatched的位置，以j+1…patlen 为subpat的“重现位置”。 rpr(j) = max{k| k<=patlen && [pat(j+1) ... pat(patlen)]= [pat(k) ... pat(k+patlen-j-1)] && (k<=1 || pat(k-1) != pat(j) } rpr(patlen)=patlen。 其中对于“=”的判断，要么pat(x)=pat(j)要么pat(x)=NULL要么pat(y)=NULL。举个例子就明白了： 下面解释rpr(j)： 上图您能接受么？呵呵，$表示空元素。例如j=1时，要跟pat[j+1]…pat[patlen]匹配，那么pat[k]…p[k+patlen-j-1]最多就是如图所示，此时k+patlen-j-1=3即k+9-1-1=3，于是k= -4，k再大您可以试试，不好使了就。其它依此类推。读者可练习求一下下面这个rpr(j)。 OK，如何求滑动距离k呢？现在小指针指在j的位置上，“重现位置”在rpr(j)，那么k=j+1-rpr(j)，小指针需要挪至最后所以k+m={j+1-rpr(j)}+{patlen-j}=patlen+1-rpr(j)，即有delta2(j)=patlen+1-rpr(j)。 总结：从3、4可以得到， 末m个元素已经匹配的情况，string需要右滑多少呢？计算delta1(string(i)),delta2(j)，谁大取谁，就说滑的越多越好，反正都有匹配不上的理由。 OK，现在给出算法伪码，加油，就快结束了： 实现上，可以更快一点。看到delta0()不要惊讶，它和delta1()基本相同，除了delta0(pat(patlen))被设置为>stringlen+patlen的一个数。因为1、2两种case 在匹配中遇到的频率很高，我们抽出fast部分，匹配时间的70%-80%都在走fast部分。自己举个例子把伪码过一遍，不明白地方跟帖。 别地儿都称“坏字符规则” “好后缀规则”，嘛回事？fatdog如是写： 哈哈，好不好笑？坏字符规则就是我们的delta1(char)计算，好后缀规则 就是我们的delta2(j)计算，本来就一码事儿。 //预处理 计算bmGS[]和bmBC[]表；//BM的Good Suffix、Bad Character while(text { //从当前匹配点text开始匹配关键词 for(i=m;(i>=0)&&(text[i]=pattern[i]);i--) ; if(i<0) { //匹配成功 报告一个成功的匹配; text+=bmGS[0];//选择下一个匹配入口点 } else//匹配失败，此时i指示着不匹配的位置点text[i]!=pat[i] { //使用两种启发式方法选择下一个匹配入口点 text+=Max(bmGS[i]-m+1,bmBC[i]); } } BM通常是sublinear的复杂度，最好O(n/m)，最坏O(n)。一般会匹配string 中的c*(i+patlen)个字符，其中c<1，并且patlen越大c越小，通常在longer pat 下BM表现更出色。 BM算法概念 BM算法是一种精确字符串匹配算法（区别于模糊匹配）。 BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。 BM算法思想 1、三个shift函数：d1,d2,d3，函数的作用是决定当匹配不成功时窗口的移动位数。 2、假设一个情况：已经读入了一个既是搜索窗口中的文本的后缀，同时也是模式串后缀的字符串u,并且读入的下一个文本字符σ与模式串的下一个字符a不相等。 3、窗口安全移动是指窗口移动意味着读入新的字符，放弃上一个窗口的前面几个字符，要保证放弃的字符确实无法参与匹配。窗口移动方向是从前向后。算法的核心思想是对于模式串，可能至少有2个相同部分，这些部分肯定有一个在模式串的后缀，其它的部分可能在模式串的中间，也可能在模式串的前缀，在后缀搜索时，发现了文本串和模式串的部分匹配X，此时，如果模式串除了后缀外，其它部分还含有X，则使文本串和模式中发生不匹配的读入的字符加上原来的匹配的X形成的部分有可能与模式串其它部分的X发生匹配（如果与模式串所有的X不匹配，则说明这个窗口内不可能发生匹配），安全地向后移动窗口，放弃的部分肯定不会发生匹配了。 1）d1:后缀u在模式串p中的另一个位置是最右出现位置是j（不包括在模式串尾的出现）,文本串的窗口安全移动方法是将窗口移动m-j字符，使文本中的u 与模式串中最右边的u的出现位置相对齐。对模式中的每个后缀，计算它到它的下一个出现之间的距离，即shift的d1，如果P的后缀u不在P中重复出现，则d1(u)被置为模式串长度m 2）d2:后缀u不出现在p中的任何其他位置。但u的后缀v可能是模式串p的一个前缀，需要对模式串所有的后缀计算第二个函数d2。对于P的每个后缀u,d2(u)表示既是P的前缀，同时也是u的后缀的最长字符串v的长度. 3）d3:在搜索窗口中从后向前搜索时，在文本字符σ处不能成功匹配。保证下一 次验证时文本字符σ一定与模式串中的一个字符σ相对应（即：使上次匹配不成功的那个字符能在模式串的第二个X部分匹配成功，在模式串中找到这个字符，该字符是X的前面一个字符），对每个字母表中的每个字符σ，d3(σ)表示σ在模式串的最右出现位置到模式串末尾的距离，如果σ不在P中，d3为m 4、读入文本字符串u并在字符σ上不匹配时，进行如下几次比较： 1）第一次：取d1(u)和d3(σ)中较大值。 2）第二次:以上面的比较结果与m-d2(u)中的较小者，因为后者是最大的安全移动距离。 5、如果抵达了窗口的起始位置，说明发现阶段一个成功匹配，用d2计算窗口的下一次移动距离，进行继续匹配。 BM算法的基本流程图解 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，如下图所示: 若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 下面，来详细介绍一下坏字符规则和好后缀规则。 首先，诠释一下坏字符和好后缀的概念。 请看下图： 模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” 五、详细设计 #include int KMPFindImprove(String &P); //改进的KMP匹配算法 void Output2(); //输出子串在主串中出现的位置 }; int String::KMPFindImprove(String &P) { int sum=0; int j=KMPFindImprove(0,P); while(j!=-1) { count[sum++]=j; if(j<=n-P.n) j=KMPFindImprove(j+P.n,P); } return sum; } void String::Output2() //输出子串在主串中的位置 { int i=0; while(count[i]!=count[i+1] && i 实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 参考程序: #include "stdio.h" void GetNext1(char *t,int next[])/*求模式t的next值并寸入next数组中*/ { int i=1,j=0; next[1]=0; while(i<=9)//t[0] { if(j==0||t[i]==t[j]) {++i; ++j; next[i]=j; } else j=next[j]; } } void GetNext2(char *t , int next[])/* 求模式t 的next值并放入数组next中 */ { int i=1, j = 0; next[1]= 0; /* 初始化 */ while (i<=9) /* 计算next[i+1] t[0]*/ { while (j>=1 && t[i] != t[j] ) j = next[j]; i++; j++; if(t[i]==t[j]) next[i] = next[j]; else next[i] = j; } } void main() { char *p="abcaababc"; int i,str[10]; GetNext1(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); GetNext2(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); printf("\n\n"); } 实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： 关于快速高效的模式匹配算法的剖析与改进 摘要：模式匹配算法是现代化网络入侵检测中的关键环节，本文主要介绍了几种常用的模式匹配算法，并在此基础上，提出一种更快捷、更高效的改进方法，以提高模式匹配的效率与质量，确保网络安全。 关键词：模式匹配入侵检测改进 随着我国计算机与网络技术的飞速发展，网络应用已涉及到人们生产、生活的各个领域，其重要性日益凸显。随之而来的网络攻击问题也备受关注，给网络安全性带来挑战。传统的网络防御模式，主要采取身份认证、防火墙、数据加密等技术，但是与当前网络发展不适应。在此背景下，入侵检测技术营运而生，并建立在模式匹配基础上，确保检测的快捷性、准确性，应用越来越广泛。 1、模式匹配原理概述 模式匹配是入侵检测领域的重要概念，源自入侵信号的层次性。结合网络入侵检测的底层审计事件，从中提取更高层次的内容。通过高层事件形成的入侵信号，遵循一定的结构关系，将入侵信号的抽象层次进行具体划分。入侵领域大师kumar将这种入侵信号划分为四大层次，并将每一个层次与匹配模式相对应。以下将分别对四大层次进行分析： (1)存在。只要存在审计事项，就可以证明入侵行为的发生，并深层次挖掘入侵企图。存在主要对应的匹配模式就是“存在模式”。可以说，存在模式就是在固定的时间内，检查系统中的特定状态， 同时判断系统状态。 (2)序列。一些入侵的发生，是遵循一定的顺序，而组成的各种行为。具体表现在一组事件的秩序上。序列对应的是“序列模式”，在应用序列模式检测入侵时，主要关注间隔的时间与持续的时间。 (3)规则。规则表示的是一种可以扩展的表达方式，主要通过and 逻辑表达来连接一系列的描述事件规则。一般适用于这种模式的攻击信号由相关活动组成，这些活动之间往往不存在事件的顺序关系。 (4)其他。其他模式是不包含前面几种方法的攻击，在具体应用过程中，难以与其他入侵信号进行模式匹配，大多为部分实现方式。 2、几种常用的模式匹配算法 2.1 ac算法 ac算法（aho-corasick）是一种可以同时搜索若干个模式的匹配算法，最早时期在图书馆书目查询系统中应用，效果良好。通过使用ac算法，实现了利用有限状态自动机结构对所有字符串的接收过程。自动机具有结构性特征，且每一个前缀都利用唯一状态显示，甚至可同时应用于多个模式的前缀中。如果文本中的某一个字符不属于模式中预期的下一个字符范围内，或者可能出现错误链接的指向状态等，那么最长模式的前缀同时也可作为当前状态相对应的后缀。ac算法的复杂性在于o（n），预处理阶段的复杂性则在于o（m）。在采取ac算法的有限状态自动机中，应该在每一个字符的模式串中分别建立节点，提高该算法的使用效率与质量。目前，应用有限 竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1； } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m). //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; } Boyer-Moore 经典单模式匹配算法 BM模式匹配算法-原理（图解） 由于毕业设计（入侵检测）的需要，这两天仔细研究了BM模式匹配算法，稍有心得，特此记下。 首先，先简单说明一下有关BM算法的一些基本概念。 BM算法是一种精确字符串匹配算法（区别于模糊匹配）。 BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。 BM算法的基本流程: 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，如下图所示: 若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 下面，来详细介绍一下坏字符规则和好后缀规则。 首先，诠释一下坏字符和好后缀的概念。 请看下图： 图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。 1）坏字符规则（Bad Character）： 在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论： i. 如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。 ii. 如果x在模式P中出现且出现次数>=1，则以该字符所在最右边位置进行对齐。 用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。 可以总结为字符x出现与否，将max(x)=0作为初值即可。 例1： 下图红色部分，发生了一次不匹配。 计算移动距离Skip(c) = m-max(c)=5 - 3 = 2，则P向右移动2位。 移动后如下图： 2）好后缀规则（Good Suffix）： 若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论： i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。 ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。 个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了，确实说得很“详细”，耐心地把它看完肯定会有所收获的～～，另外有关模式函数值next[i]确实有很多版本啊，在另外一些面向对象的算法描述书中也有失效函数f(j)的说法，其实是一个意思，即next[j]=f(j-1)+1，不过还是next[j]这种表示法好理解啊： KMP字符串模式匹配详解 KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 模式匹配算法 源程序如下： #include printf("匹配的结果:%d\n",n); } //KMP模式匹配算法 int index_KMP(char *s,char *t,int pos) { int i=pos,j=1; while (i<=(int)strlen(s)&&j<=(int)strlen(t)) { if (j==0||s[i]==t[j-1]) { i++; j++; } else j=next[j]; } if(j>(int)strlen(t)) return i-strlen(t)+1; else return 0; } void get_next(char *t,int *next) { int i=1,j=0; next[0]=next[1]=0; while (i<(int)strlen(t)) { if (j==0||t[i]==t[j]) { i++; j++; next[i]=j; } else j=next[j]; } } 运行效果如下： /** *时间：2010年8月26日7:09:57 *功能：模式匹配算法代码 */ #include"stdio.h" #include"malloc.h" void kmp(int *ikmp,char *t,int t_length) { int k=0; int q=0; ikmp[0]=k; for(q=1;q while(t[t_length]!='\0') { t_length++; } /*测试*/ printf("t_length is %d\n",t_length); /*求t的kmp值*/ ikmp=malloc(t_length*sizeof(int)); kmp(ikmp,t,t_length); /*匹配过程*/ for(q=0;q 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS); int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 简单的模式匹配算法_Brute-Force算法 在串的操作中，子串的定位操作Index_string(s，t)，通常称之为模式匹配(其中：子串t称之为模式串)。其功能是：主串s＝“c0c1...c n-1”中，去查找子串t＝“t0t1...t m-1”，若找到则返回子串t在主串s中的位置,否则查找不成功，返回-1。 为了便于理解，我们举例进行说明。 1．例子 例如：主串s=”ababcabcacbab”,t=”abcac”。其匹配过程如图6－12所示。 第一趟匹配: i=2 a b a b c a b c a c b a b a b c j=2 第二趟匹配: i=1 a b a b c a b c a c b a b a j=0 第三趟匹配： i=6 a b a b c a b c a c b a b a b c a c j=4 第四趟匹配： i=3 a b a b c a b c a c b a b a j=0 第五趟匹配： i=4 a b a b c a b c a c b a b a j=0 第六趟匹配： i=10 a b a b c a b c a c b a b a b c a c j=5 图6－12 Brute-Force算法中串的匹配过程 2．算法思想 算法的基本思想是：分别设置计数指针i和j指示主串s和模式串t中当前正待比较的字符位置。从主串的第一个字符和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较。依次类推，直到模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，函数值为和模式串中第一个字符相等的字符在主串中的序号，否则称匹配不成功。 这个算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后只要有一个字符比较不等便需回溯。 串的匹配算法——Brute Force (BF)算法 匹配模式的定义 设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。通常把主串S称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串S中找到一个模式串T；不成功则指目标串S中不存在模式串T。 BF算法 Brute-Force算法简称为BF算法，其基本思路是：从目标串S的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串S的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串S中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0. /*T非空。 int index(String S, String T ,int pos) { int i=pos; //用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配int j =1; //j用于子串T中当前位置下标值 while(i<=S[0]&&j<=T[0]) //若i小于S长度且j小于T的长度时循环 { if(S[i]==T[j]) //两个字母相等则继续 { ++i； ++j； } else //指针后退重新开始匹配 { i=i-j+2; //i退回到上次匹配首位的下一位 j=1； } if(j>T[0]) return i-T[0]; else return 0; } } BF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m 次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m 从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是O(n+m). 宜宾学院学报 Journal of Yibin University 优先数字出版 —————————————————————— 收稿日期：2014-07-03 2014-09-05 基金项目：安徽电子信息职业技术学院教科研项目“基于数据挖掘技术的高职院校招生决策系统研究与应用” （ADZX1306） 作者简介：余飞（1983-），男，硕士，讲师，研究方向为计算机网络安全、数据挖掘、分布式操作系统 网络出版时间： 网络出版地址： 基于特征值的模式匹配算法 余 飞，刘思宏 （安徽电子信息职业技术学院 软件学院，安徽蚌埠233060） 摘 要：模式匹配算法广泛应用于防火墙、入侵检测等网络安全领域，其算法效能直接影响到系统的工作效率．本文首次提出了一种基于特征值的模式匹配算法——FLC （First-Last-Characters ）算法．该算法打破了经典算法有序偏移的思想，突破了BMHS （Boyer-Moore-Horspool-Sunday ）算法最大偏移量（m+1）的上限，从而增大了偏移距离，减 则匹配成功；若有一个字符不同，则匹配不成功，模式串向右移动一个字符的位置，继续比较，直到将文本串的所有位都比较过来．BF 算法实现简单，但模式串每次仅偏移一个字符，这导致模式串几乎要与文本串中的每一个字符进行比较，运行效率极其低下． KMP 算法[2]是BF 的一种改进算法，该算法由Knuth 等人提出．KMP 算法根据给定的模式串，定义一个next 函数．模式串与文本串按顺序进行从左到右匹配， 2014-09-12 13:00 https://www.sodocs.net/doc/49565603.html,/kcms/detail/51.1630.Z.20141211.1054.008.html 一、实验内容和目的 1、深刻理解并掌握蛮力算法的设计思想； 2、提高应用蛮力算法设计算法的技能； 3、理解这样一个观点:用蛮力法设计的算法，一般来说，经过适度的努 力后，都可以对算法的第一个版本进行一定程度的改良，改进其时 间性能。 二、实验原理及基本技术路线图（方框原理图） 串匹配问题——给定两个串S=“s1s2…s n” 和T=“t1t2…t m”，在主 串S中查找子串T的过程称为串匹配，也称模式匹配。 串匹配问题属于易解问题。 串匹配问题的特征： （1）算法的一次执行时间不容忽视：问题规模n 很大，常常需要在 大量信息中进行匹配； （2）算法改进所取得的积累效益不容忽视：串匹配操作经常被调用，执行频率高。 BF算法： 基本思想：从主串S的第一个字符开始和模式T的第一个字符进行比 较，若相等，则继续比较两者的后续字符；若不相等，则从主串S 的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，若T中的字符全部比较完毕，则说明本趟匹配成功；若最后一轮匹配 的起始位置是n-m，则主串S中剩下的字符不足够匹配整个模式T， 匹配失败。这个算法称为朴素的模式匹配算法，简称BF算法。 KMP算法： 1. 在串S和串T中分别设比较的起始下标i和j； 2. 循环直到S中所剩字符长度小于T的长度或T中所有字符均比较 完毕 2.1 如果S[i]=T[j]，则继续比较S和T的下一个字符；否则 2.2 将j向右滑动到next[j]位置，即j=next[j]； 2.3 如果j=0，则将i和j分别加1，准备下一趟比较； 2.4 如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0； BM算法： BM算法与KMP算法的主要区别是匹配操作的方向不同。虽然BM算法仅把匹配操作的字符比突顺序改为从右向左，但匹配发生失败时，模式T右移的计算方法却发生了较大的变化。 设计思想：设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 3113008094 詹宏宇信安1 简单匹配算法： ?算法设计思想：等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 ?将主串S的第pos个字符和模式T的第1个字符比较， –若相等，继续逐个比较后续字符； –若不?直到主串S的一个连续子串字符序列与模式T相等。返回值为S 中与T匹配的子序列第一个字符的序号，即匹配成功。 ?否则，匹配失败，返回值0 . int Find(char*target, char* pat) { inti=0,j=0; int lengthP=strlen(pat), lengthT=strlen(target); while(i<=lengthT-lengthP) { j=0; while(target[i]==pat[j]&&j Kmp算法实现： 第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来； 第二步：执行定位函数Index_kmp（与BF算法模块非常相似） 1. int KMPindex(SString S, SString T, int pos) 2. { 3. if (pos <1 || pos > S[0] ) exit(ERROR); 4. int i = pos, j =1; 5. while (i<= S[0] && j <= T[0]) 6. { 7. if (S[i] == T[j]) { 8. ++i; ++j; 9. } else { 10. j = next[j+1]; 11. } 12. } 13. if(j > T[0]) return i - T[0]; 14. return ERROR; 15. } 完整实现代码： // Test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include 模式匹配的KMP算法详解
字符串的模式匹配算法
模式匹配算法的设计与实现
实验三____串的模式匹配
模式匹配KMP算法实验报告
关于快速高效的模式匹配算法的剖析与改进
串的模式匹配算法实验报告
串的朴素模式匹配算法(BF算法)
BM模式匹配算法图解
KMP字符串模式匹配算法解释
模式匹配KMP算法实验步骤
数据结构-模式匹配算法
模式匹配算法
C语言字符串模式匹配
字符串匹配算法总结
简单的模式匹配算法
串的模式匹配算法
基于特征值的模式匹配算法
串匹配问题：BF算法、KMP算法、BM算法
简单匹配算法
相关文档
- 串的模式匹配问题实验总结(用C实现)
- C语言 字符串匹配算法
- 实验三____串的模式匹配
- 字符串匹配算法总结
- 模式匹配算法的原理及应用
- 数据结构串的模式匹配实验报告
- 数据结构 -第5周串第2讲-串的模式匹配
- 串的模式匹配算法
- 知识点串的模式匹配
- 串匹配BM算法、KMP算法、BF算法
- 字符串的模式匹配算法
- C语言字符串模式匹配
- 串匹配问题,算法分析与设计答案
- 知识点串的模式匹配
- 第5周串第2讲-串的模式匹配
- 串匹配问题：BF算法、KMP算法、BM算法
- 数据结构- 串的模式匹配算法：BF和 KMP算法
- 《KMP 字符串模式匹配算法》教学课例
- 模式匹配的KMP算法详解
- 第4章串第2讲-串的模式匹配