数据结构- 串的模式匹配算法：BF和 KMP算法
数据结构- 串的模式匹配算法：BF和KMP算法
Brute-Force算法的思想
Brute-Force算法的基本思想是：
1) 从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。
2) 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
Brute-Force算法的实现
c语言实现：
1.// Test.cpp : Defines the entry point for the console application.
2.//
3.#include "stdafx.h"
4.#include
5.#include "stdlib.h"
6.#include
https://www.sodocs.net/doc/8714220475.html,ing namespace std;
8.
9.//宏定义
10.#define TRUE 1
11.#define FALSE 0
12.#define OK 1
13.#define ERROR 0
14.
15.#define MAXSTRLEN 100
16.
17.typedef char SString[MAXSTRLEN + 1];
18./************************************************************************/
19./*
20.返回子串T在主串S中第pos位置之后的位置，若不存在，返回0
21.*/
22./************************************************************************/
23.int BFindex(SString S, SString T, int pos)
24.{
25.if (pos <1 || pos > S[0] ) exit(ERROR);
26.int i = pos, j =1;
27.while (i<= S[0] && j <= T[0])
28. {
29.if (S[i] == T[j])
30. {
31. ++i; ++j;
32. } else {
33. i = i- j+ 2;
34. j = 1;
35. }
36. }
37.if(j > T[0]) return i - T[0];
38.return ERROR;
39.}
40.
41.
42.
43.void main(){
44. SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b
'};
45. SString T = {5,'a','b','c','a','c'};
46.int pos;
47. pos = BFindex( S, T, 1);
48. cout<<"Pos:"< 49.} 2.1 算法思想： 每当一趟匹配过程中出现字符比较不等时，不需要回溯I指针，而是利用已经的带的“部分匹配”的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。 即尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ ②模式应该向右滑多远才是高效率的? 现在讨论一般情况: 假设主串：s: …s(1)s(2) s(3) ……s(n)? ; 模式串：p: …p(1)p(2) p(3)…..p(m)? 现在我们假设主串第i个字符与模式串的第j(j<=m)个字符…失配?后，主串第i个字符与模式串的第k(k 此时，s(i)≠p(j)： 由此，我们得到关系式：即得到到1 到 j -1 的"部分匹配"结果: ‘P(1)P(2) P(3)…..P(j-1)’= ’ S(i-j+1)……S(i-1)’ 从而推导出k 到j- 1位的“部分匹配”：即P的j-1～j-k＝S前i-1～i- (k -1)) 位 ‘P(j - k + 1) …..P(j-1)’ = ’S(i-k+1)S(i-k+2)……S(i-1)’ 由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在k?>k满足下列关系式：(k 有关系式：即(P的前k- 1 ~ 1位＝S前i-1～i-(k-1) )位) ,： ‘P(1) P(2) P(3)…..P(k-1)’= ’S(i-k+1)S(i-k+2)……S(i-1)’ 现在我们把前面总结的关系综合一下,有： 由上，我们得到关系： ‘p(1)p(2) p(3)…..p(k-1)’ = ‘p(j - k + 1) …..p(j-1)’ 反之，若模式串中满足该等式的两个子串，则当匹配过程中，主串中的第i 个字符与模式中的第j个字符等时，仅需要将模式向右滑动至模式中的第k个字符和主串中的第i个字符对齐。此时，模式中头k-1个字符的子串…p(1)p(2) p(3)…..p(k-1)?必定与主串中的第i 个字符之前长度为k-1 的子串?s(j-k+1)s(j-k+2)……s(j-1)?相等，由此，匹配仅需要从模式中的第k 个字符与主串中的第i 个字符比较起继续进行。若令next[j] = k ,则next[j] 表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行的比较的位置。由此可引出模式串的next函数： 根据模式串P的规律：‘p(1)p(2) p(3)…..p(k-1)’ = ‘p(j - k + 1) …..p(j-1)’ 由当前失配位置j(已知) ，可以归纳计算新起点k的表达式。 由此定义可推出下列模式串next函数值： 模式匹配过程: 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.} 完整实现代码： 1.// Test.cpp : Defines the entry point for the console application. 2.// 3.#include "stdafx.h" 4.#include 5.#include "stdlib.h" 6.#include https://www.sodocs.net/doc/8714220475.html,ing namespace std; 8. 9.//宏定义 10.#define TRUE 1 11.#define FALSE 0 12.#define OK 1 13.#define ERROR 0 14. 15.#define MAXSTRLEN 100 16. 17.typedef char SString[MAXSTRLEN + 1]; 18. 19.void GetNext(SString T, int next[]); 20.int KMPindex(SString S, SString T, int pos); 21./************************************************************************/ 22./* 23.返回子串T在主串S中第pos位置之后的位置，若不存在，返回0 24.*/ 25./************************************************************************/ 26.int KMPindex(SString S, SString T, int pos) 27.{ 28.if (pos <1 || pos > S[0] ) exit(ERROR); 29.int i = pos, j =1; 30.int next[MAXSTRLEN]; 31. GetNext( T, next); 32.while (i<= S[0] && j <= T[0]) 33. { 34.if (S[i] == T[j]) { 35. ++i; ++j; 36. } else { 37. j = next[j]; 38. } 39. } 40.if(j > T[0]) return i - T[0]; 41.return ERROR; 42.} 43. 44./************************************************************************/ 45./* 求子串next[i]值的算法 46.*/ 47./************************************************************************/ 48.void GetNext(SString T, int next[]) 49.{ int j = 1, k = 0; 50. next[1] = 0; 51.while(j < T[0]){ 52.if(k == 0 || T[j]==T[k]) { 53. ++j; ++k; next[j] = k; 54. } else { 55. k = next[k]; 56. } 57. } 58.} 59. 60.void main(){ 61. SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b '}; 62. SString T = {5,'a','b','c','a','c'}; 63.int pos; 64. pos = KMPindex( S, T, 1); 65. cout<<"Pos:"< 66.} 2.2 求串的模式值next[n] k值仅取决于模式串本身而与相匹配的主串无关。 我们使用递推到方式求next函数： 1）由定义可知： next[1] = 0; 2) 设next[j] = k ,这个表面在模式串中存在下列关系： ‘P(1) ….. P(k-1)’ = ‘P(j - k + 1) ….. P(j-1)’ 其中k为满足1< k ‘P(1) ….. P(k`-1)’ = ‘P(j - k` + 1) ….. P(j-1)’ 此时next[j+1] = ?可能有两种情况： （1）若Pk = Pj，则表明在模式串中： ‘P(1) ….. P(k)’ = ‘P(j - k + 1) ….. P(j)’ 并且不可能存在k` > 满足：‘P(1) ….. P(k`)’ = ‘P(j - k` + 1) ….. P(j)’ 即next[j+1] = k + 1推到=》： next[j+1] = next[j] + 1; (2) 若Pk Pj 则表明在模式串中： ‘P(1) ….. P(k)’ ‘P(j - k + 1) ….. P(j)’ 此时可把next函数值的问题看成是一个模式匹配的问题，整个模式串即是主串又是模式串， 而当前匹配的过程中，已有： Pj-k+1 = P1，Pj-k+2 = P2，... Pj-1 = Pk-1. 则当Pk Pj时应将模式向右滑动至以模式中的第next[k]个字符和主串中的第j 个字符相比较。 若next[k] = k`,且Pj= Pk`, 则说明在主串中的第j+1 个字符之前存在一个长度为k` (即next[k])的最长子串，和模式串 从首字符其长度为看k`的子串箱等。即 ‘P(1) ….. P(k`)’ = ‘P(j - k` + 1) ….. P(j)’ 也就是说next[j+1] = k` +1即 next[j+1] = next[k] + 1 同理，若Pj Pk` ,则将模式继续向右滑动直至将模式串中的第next[k`]个字 符和Pj对齐， ... ,一次类推，直至Pj和模式中某个字符匹配成功或者不存在k`(1< k` < j)满足，则: next[j+1] =1; 1./************************************************************************/ 2./* 求子串next[i]值的算法 3.*/ 4./************************************************************************/ 5.void GetNext(SString T, int next[]) 6.{ int j = 1, k = 0; 7. next[1] = 0; 8.while(j < T[0]){ 9.if(k == 0 || T[j]==T[k]) { 10. ++j; ++k; next[j] = k; 11. } else { 12. k = next[k]; 13. } 14. } 15.} next 函数值究竟是什么含义，前面说过一些，这里总结。 设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n], 1.next[n] = 0 表示S[m]和T[1]间接比较过了，不相等，下一次比较 S[m+1] 和T[1] 2.next[n] =1 表示比较过程中产生了不相等，下一次比较 S[m] 和T[1]。 3.next[n] = k >1 但k 等了，下一次比较S[m]和T[k]相等吗？ 4.其他值，不可能。 注意： （1）k值仅取决于模式串本身而与相匹配的主串无关。 （2）k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。 （3）这里的两部分子串可以有部分重叠的字符，但不可以全部重叠。 next[j]函数表征着模式P中最大相同前缀子串和后缀子串（真子串）的长度。 可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。 即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。 模式匹配的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、掌握串的两种模式匹配算法：BF和KMP。 3、了解串的应用。 【实验学时】 2学时 【实验预习】 回答以下问题： 1、串和子串的定义 串的定义：串是由零个或多个任意字符组成的有限序列。 子串的定义：串中任意连续字符组成的子序列称为该串的子串。 2、串的模式匹配 串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串，从主串s的第start个字符开始查找等于子串t的过程称为模式匹配，如果在S中找到等于t的子串，则称匹配成功，函数返回t在s中首次出现的存储位置（或序号）；否则，匹配失败，返回0。 【实验内容和要求】 1、按照要求完成程序exp4_1.c，实现串的相关操作。调试并运行如下测试数据给出运行结果： ?求“This is a boy”的串长； ?比较”abc 3”和“abcde“； 表示空格 ?比较”english”和“student“； ?比较”abc”和“abc“； ?截取串”white”，起始2，长度2； ?截取串”white”，起始1，长度7； ?截取串”white”，起始6，长度2； ?连接串”asddffgh”和”12344”； #include typedef struct { char data[MAXSIZE]; int length; } SqString; int strInit(SqString *s); /*初始化串*/ int strCreate(SqString *s); /*生成一个串*/ int strLength(SqString *s); /*求串的长度*/ int strCompare(SqString *s1,SqString *s2); /*两个串的比较*/ int subString(SqString *sub,SqString *s,int pos,int len); /*求子串*/ int strConcat(SqString *t,SqString *s1,SqString *s2); /*两个串的连接*/ /*初始化串*/ int strInit(SqString *s) { s->length=0; s->data[0]='\0'; return OK; }/*strInit*/ /*生成一个串*/ int strCreate(SqString *s) { printf("input string :"); gets(s->data); s->length=strlen(s->data); return OK; }/*strCreate*/ /*（1）---求串的长度*/ int strLength(SqString *s) { return s->length; }/*strLength*/ /*（2）---两个串的比较，S1>S2返回>0，s1 实验三串的模式匹配 一、实验目的 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 对KMP算法的理解 整理者——戴红伟 字符匹配算法的现实意义：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。 （请同时参照课本P53～54相关内容） 1.要理解next[j]=k 中，k的含意； （1）BF算法 假设有字符串 S=S1S2......S N P=P1P2......P M 其中（M （2）KMP算法 为了解决上述的问题，KMP算法被发现。 KMP算法的思想如下。匹配过程中，出现不匹配时，S的指针不进行回朔（原地不动），将P尽可能地向后移动一定的距离，再进行匹配。 如图： （该图引用自互联网） 从上图中我们看到，当S移动到i，P到j的时候失配。这时候i不回朔，而只是将P 向前移动尽可能的距离，继续比较。 假设，P向右移动一定距离后，第k个字符P[k]和S[i]进行比较。 此时如上图，当P[j]和S[i]失配后，i不动，将P前移到K，让P[k]和S[i]继续匹配。现在的关键是K的值是多少？ 通过上图，我们发现，因为黄色部分表示已经匹配了的结果（因为是到了S[i]和P[j]的时候才失配，所以S i-j+1S i-j+2…S i-1 = P1P2…P j-1，见黄色的部分）。所以有： 1、S i-k+1S i-k+2…S i-1 = P j-k+1P j-k+2…P j-1。 所以当P前移到K时，有： 2、S i-k+1S i-k+2…S i-1 = P1P2…P k-1。 通过1，2有 P j-k+1P j-k+2…P j-1 = P1P2…P k-1。 呵呵，此时我们的任务就是求这个k值了。。。 参考：https://www.sodocs.net/doc/8714220475.html,/2008-09/122068902261358.html 2.求出k 值 按照课本的求法就可以处理。 课本是已知前j个元素的“前缀函数值”，如何求的j+1个元素的前缀函数值。这里有一个思路要发生转变的地方，把一个模式串分成两个部分，因为我们要找k使得P j-k+1P j-k+2…P j-1= P1P2…P k-1，而这本身就是一个模式匹配问题，所以把模式串的前边部分的子串当作“新的模式串”，这样就很容易理解为什么当t k!=t j时，t1…t next[k]-1 = t j-（next[k]-1）…t j-1了。因为这时候t k匹配失败，需要进一步移动模式子串，所以移动的位置就是next[k]。 实验报告 课程数据结构实验名称实验三串 学号姓名实验日期： 串的操作 实验目的： 1. 熟悉串类型的实现方法，了解简单文字处理的设计方法； 2. 熟悉C语言的字符和把字符串处理的原理和方法； 3. 熟悉并掌握模式匹配算法。 实验原理： 顺序存储结构下的关于字符串操作的基本算法。 模式匹配算法BF、KMP 实验内容： 4-19. 在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。 4-20. 设串采用静态数组存储结构，编写函数实现串的替换Replace（S，start，T，V），即要求在主串S中，从位置start开始查找是否存在字串T。若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0；并要求设计主函数进行测试。一个测试例子为：S=“I am a student”,T=“student”,V=“teacher”。程序代码： 4-19的代码： /*静态存储结构*/ typedef struct { char str[MaxSize]; int length; }String; /*初始化操作*/ void Initiate(String *S) { S->length=0; } /*插入子串操作*/ int Insert(String *S, int pos, String T) /*在串S的pos位置插入子串T*/ { int i; if(pos<0||pos>S->length) { printf("The parameter pos is error!\n"); return 0; } else if(S->length+T.length>MaxSize) 简单的模式匹配算法_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在若干个字符序列比较相等后只要有一个字符比较不等便需回溯。模式匹配的KMP算法详解
字符串的模式匹配算法
模式匹配算法的设计与实现
数据结构实验报告-串
实验三____串的模式匹配
模式匹配KMP算法实验报告
关于快速高效的模式匹配算法的剖析与改进
串的模式匹配算法实验报告
串的朴素模式匹配算法(BF算法)
BM模式匹配算法图解
KMP字符串模式匹配算法解释
模式匹配KMP算法实验步骤
数据结构-模式匹配算法
模式匹配算法
C语言字符串模式匹配
字符串匹配算法总结
KMP算法-如何理解
数据结构串的操作实验报告
简单的模式匹配算法