精华内容
下载资源
问答
  • 字符串朴素模式匹配算法(简单模式匹配算法)
    千次阅读
    2020-08-08 19:41:45

    字符串朴素模式匹配算法

    一、朴素模式匹配算法(简单模式匹配算法)思想:

    将主串中与模式串长度相同的子串搞出来,挨个与模式串对比
    当子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串
    若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较
    最坏时间复杂度: O(nm)
    最坏情况:每个子串的前m-1个字符都和模式串匹配,只有第m个字符不匹配
    比较好的情况:每个子串的第1个字符就与模式串不匹配

    二、代码实现

    方案一:

    //方案① 
    int Index(String S,String T){
    	int i,j;
    	int k=1;
    	while(i<=S.length&&j<=T.length){
    		if(S.ch[i]==T.ch[j]){
    			i++;
    			j++
    		}
    		else{
    			i=k;
    			j=1;
    			k++;
    		}
    	}
    	if(j>T.length){
    		return k;
    	}
    	else return 0;
    }
    

    方案二:

    //方案② 
    int Index(String S,String T){
    	int i,j;
    	while(i<=S.length&&j<=T.length){
    		if(S.ch[i]==T.ch[j]){
    			i++;
    			j++
    		}
    		else{
    			i=i-j+2;
    			j=1;
    		}
    	}
    	if(j>T.length){
    		return i-T.length;
    	}
    	else return 0;
    }
    
    更多相关内容
  • 实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
  • 全面综述了应用于入侵检测系统的经典的模式匹配算法,包括单模式匹配算法中的KMP算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC—BM算法,并对各种算法的执行效率进行了总结。通过分析算法的思想,提出了未来...
  • 基于字符串模式匹配算法的病毒感染检测问题——C语言实现。
  • 串的模式匹配算法

    2019-03-25 10:30:09
    1、掌握串的存储表示及基本操作; 2、掌握串的两种模式匹配算法:BF和KMP。 3、了解串的应用。
  • 恐怕现在用过电脑的人,一定都知道大部分带文本编辑功能的软件都有一个快捷键ctrl+f 吧(比如word)。这个功能主要来完成“查找”,“替换”和...这就是模式匹配的定义啦,下面来看看怎么实现模式匹配算法吧。2.朴
  • 《数据结构(C语言版 第2版)》严蔚敏 实验四 基于字符串模式匹配算法的病毒感染检测问题,含实验报告
  • 针对Wu-Manber多模式匹配算法所存在的匹配效率低、跳转距离较小的问题,结合PDF文本内容的编码规则,提出了一种适用于中文PDF文本内容审查的Wu-Manber改进算法。该算法使用布隆过滤器提取模式串关键信息,同时结合...
  • 这是重庆大学数据结构实验报告,题目是串的操作与KMP模式匹配算法。里面有完整的实验流程,包括源码及结果截屏
  • 模式匹配算法

    2014-06-04 09:02:19
    数据库中模式匹配算法的实现(代码+运行结果)的实验报告
  • 基于FPGA设计一个能够检测出重叠...首先从KMP字符串模式匹配算法出发,推导出next函数值与序列检测器状态之间的关系,并针对匹配串重叠的情况进行修改,得到有限状态机的状态转换图,最后用VHDL语言描述并仿真验证。
  • KMP模式匹配算法

    2016-07-05 22:07:06
    讲解完成了KMP模式匹配算法用于查找字符串
  • 针对Aho-Corasick(AC)多模式匹配算法使用大的空间复杂度代价换取小的时间复杂度,提出一种改进算法降 低AC多模式匹配算法的空间复杂度,使AC多模式匹配算法的空间复杂度减少10%,并实现AC多模式匹配算法在深层 报文解析...
  • 基于BF和KMP的串模式匹配算法设计与实现(C语言).rar
  • C/C++实现串匹配算法,包括源代码和实验报告。实现了串的创建,查看,修改,朴素的模式匹配算法,kmp算法和kmp改进算法。
  • 针对病毒特征检测中码串长度对模式匹配算法性能影响的问题, 结合基于码串长度的特征集自适应分类思路, 提出了两种改进的多模式精确匹配算法, 即NAC_BM和NWM_QS。改进算法通过引入文本窗口的前缀字符块WB增加了跳跃...
  • 目前大多数这方面的研究都是基于英文的,针对这种情况,探讨了中文Deep Web查询接口的模式匹配方法,并提出了一种基于《知网》、面向中文语义的模式匹配算法,并利用属性在查询接口上的相对位置信息解决语义冲突。...
  • 一种改进的串的模式匹配算法的探讨,穆维友,吴泽平,串的模式匹配算法一直都是计算机科学领域的研究焦点之一。本文首先分析了BF、KMP、BM三种算法,并提出了一种改进的Sundaynew算法,给��
  • 一种新的串模式匹配算法,韩雷钧,张凯,模式的匹配算法一直是计算机搜索领域的研究的重点工程。本文首先分析了传统的蛮力字符串匹配和增强型的Boyer-Moore算法,并提出了一�
  • 计算机网络入侵检测系统的多模式匹配算法 (1).pdf
  • 字符串与模式匹配算法 2009/03/05 内容 作业讲解 字符串概念与抽象数据类型 串模式匹配 1-1 链表插入 循环链表合并2-1 字符串基本概念 字符串简称串是一种特殊的线性表其特殊性主要在于表中的每个元素是一个字符 一...
  • 算法的时间复杂度为O(m*n),算法如下: 代码如下://朴素的串的模式匹配算法,S为主串,T为模式串,即找S中有没有与T相同的字串int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替{ ...
  • 模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的应用,BM算法以其高效的匹配过程成为模式匹配算法中应用最为广泛的算法之一。尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH...
  • 主要介绍了java 中模式匹配算法-KMP算法实例详解的相关资料,需要的朋友可以参考下
  • 为了使网络入侵检测系统能够在高速网络环境中有效的开展工作, 实现计算机网络入侵检测系统的多模式匹配算法优化设计. 首先, 对网络入侵检测的算法与原理进行全面分析. 其次, 对网络入侵检测系统多模式匹配算法的优化...
  • AC多模式匹配算法的优化与应用,孙强,辛阳,针对Aho-Corasick(AC)多模式匹配算法使用大的空间复杂度代价换取小的时间复杂度,提出一种改进算法降低AC多模式匹配算法的空间复杂度,
  • 串的模式匹配算法(KMP算法,BF算法+算法详解+实现代码) 子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置,又被称为串的模式匹配 一、BF模式匹配算法 BF算法思想:Brute-Force算法又称蛮力匹配算法...

    串的模式匹配算法(KMP算法,BF算法+算法详解+实现代码)

    子串的定位操作是找子串在主串中从第pos个字符后首次出现的位置,又被称为串的模式匹配

    一、BF模式匹配算法

    • BF算法思想:Brute-Force算法又称蛮力匹配算法(简称BF算法),从主串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则继续比较后续字符;否则回溯到主串S的第pos+1个字符开始重新和模式串T进行比较。以此类推,直至模式串T中的每一个字符依次和主串S中的一个连续的字符序列相等,则称模式匹配成功,此时返回模式串T的第一个字符在主串S中的位置;否则主串中没有和模式串相等的字符序列,称模式匹配不成功。

    • BF算法思想:
      从主串S的第pos个字符开始的子串与模式串T比较的策略是从前到后依次进行比较。因此在主串中设置指示器i表示主串S中当前比较的字符;在模式串T中设置指示器j表示模式串T中当前比较的字符。

    • 实例分析:
      给定主串为S=“ababcabcacbab”,T=“abcac”。匹配过程如下
      在这里插入图片描述

    • 实现代码:

    //BF模式匹配算法
    int Index(HString S, int pos, HString T) {
    	int i = pos;//主串从pos开始
    	int j = 1;//模式串从头开始
    	while (i <= S.len&&j <= T.len) {
    		if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
    			i++;
    			j++;
    		}
    		else {//当对应字符不相等时
    			i = i - j + 2;//主串回溯到i-j+2的位置重新比较
    			j = 1;//模式串从头开始重新比较
    		}
    	}
    	if (j > T.len) {//匹配成功时,返回匹配起始位置
    		return i - T.len;
    	}
    	else {//匹配失败,返回0
    		return 0;
    	}
    }
    
    • 算法分析:
      • BF算法的思想比较简单,但当在最坏情况下,算法的时间复杂度为O(n*m),其中n和m分别是主串和模式串的长度。这个算法的主要事件耗费在失配后的比较位置有回溯,因而比较次数过多。为降低时间复杂度可采用无回溯的算法。

    二、KMP模式匹配算法(重点)

    • KMP算法思想
      Knuth-Morris-Pratt算法(简称KMP),是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法。KMP算法是模式匹配中的经典算法,和BF算法相比,KMP算法的不同点是消除BF算法中主串S指针回溯的情况,从而完成串的模式匹配,这样的结果使得算法的时间复杂度仅为O(n+m)。
    • KMP算法描述
      KMP算法每当一趟匹配过程中出现字符比较不相等时,主串S的i指针不需要回溯,而是利用已经得到的“部分匹配”结果将模式串向右滑动一段距离后,继续进行比较 。
    • next函数
      在实现算法之前,我们需要引入next函数:若令next[j]=k,则next[j]表明当模式中第j个字符与主串中相应字符“失配”时,在模式中需重新和主串中该字符进行比较的当前字符的位置。由此引出next函数的定义:
      在这里插入图片描述
      由此可见,next函数的计算仅与模式串本身有关,和主串无关。其中’T1T2…T(k-1)'时’T1T2…T(j-1)'的真前缀子串,
      ‘T(j-k+1)T(j-k+2)…T(j-1)’是’T1T2…T(j-1)'的真后缀子串。当next函数定义中的集合不为空时,next[j]的值等于串’T1T2…T(j-1)'的真前缀子串和真后缀子串相等时的最大子串长度+1
      通过以上分析,推导出模式串"abaabcac"的next值的计算过程如下表所示.
      (1).当j=1时,由定义得知,next[1]=0;
      (2)当j=2时,满足1<k<j的k值不存在,由定义得知next[2]=1;
      在这里插入图片描述
      则我们可以得出next值
      在这里插入图片描述
    • 匹配过程如下:
      在求得模式串的next函数之后,匹配可按如下进行:假设指针i和j分别指示主串S和模式串T中当前比较的字符,令i的初始值为pos,j的初值为1。若在匹配过程中Si=Tj,则i和j分别增1;否则,i不变,而j退到next[j]位置再比较(即Si和Tnext[j]进行比较),若相等,则指针各自增1,否则j再退到下一个next值得位置,以此类推,直至下列两种可能:
      第一种:j退到某个next值(next[…next[j]])时字符比较相等,则指针各自增1继续进行匹配;
      第二种是j退到next值为0(即与模式串得第一个字符失配),则此时需将主串和模式串同时向右滑动一个位置(此时j=0,当向右滑动一个位置时,即模式串得第一个字符),即从主串得下一个字符Si+1和模式串T1重新开始比较。

      在这里插入图片描述
    • 求next[]的算法如下:
    void Get_Next(HString T, int next[]) {
    	int j = 1, k = 0;
    	next[1] = 0;
    	while (j < T.len) {
    		if (k == 0 || T.ch[j] == T.ch[k]) {
    			++j;
    			++k;
    			next[j] = k;
    		}
    		else {
    			k = next[k];
    		}
    	}
    }
    

    三、改进的KMP算法

    我们在前面介绍的next函数虽然好用,但还不够完美,在某种情况下是有缺陷的,例如如下匹配过程
    主串为"aaabaaaab" 模式串为"aaaab"
    在这里插入图片描述

    在求得模式串的next值之后,匹配过程如下:
    在这里插入图片描述
    从串的匹配过程可以看到,当i=4,j=4时,S4!=T4,由next[j]所示还需进行i=4、j=3,i=4、j=2,i=4、j=1这三次比较。实际上,因为模式串中的第1、2、3个字符和第4个字符都相等(即都是’a’),因此,不需要再和主串中第4个字符相比较,而可以直接将模式串一次向右滑动4个字符的位置直接进行i=5、j=1的判断。
    这就是说,若按上述定义得到next[j]=k,而模式串中T(j)!=T(k),则当Si != Tj时,不需要进行Si和Tk的比较,直接和Tnext[k]进行比较;换句话说,此时的next[j]的值应和next[k]相同,为此将next[j]修正为nextval[j]。而模式串中Tj !=Tk,则当Si !=Tj时,还是需要比较Si和Tk的比较,因此nextval[j]的值就是k,即nextval[j]得值就是next[j]的值。
    通过以上分析,计算第j个字符得nextval值时,要看第j个字符是否和第j个字符的next值指向的字符相等。若相等,则nextval[j]=nextval[next[j]];否则,nextval[j]=next[j]。
    由此推导出模式串T='aaaab’的nextval值的计算过程如下:

    • 当j=1时,由定义知,nextval[1]=0;
    • 当j=2时,由next[2]=1,且T2=T1,则nextval[2]=nextval[1],即nextval[2]=0;
    • 当j=3时,由next[3]=2,且T3=T2,则nextval[3]=nextval[2],即nextval[3]=0;
    • 当j=4时,由next[4]=3,且T4=T3,则nextval[4]=nextval[3],即nextval[4]=0;
    • 当j=5时,由next[5]=4,且T5不等于T4,则nextval[5]=next[5],即nextval[5]=4.
      则模式串"aaaab"的nextval函数值如下所示。
      在这里插入图片描述
    • 改进后的匹配过程如下:
      在这里插入图片描述
      可以看到匹配次数大大减少,降低了复杂度。
    • nextval函数实现代码如下
      nextval[]时基于next[]函数实现的。
    void Get_Next(HString T, int next[]) {
    	int j = 1, k = 0;
    	next[1] = 0;
    	while (j < T.len) {
    		if (k == 0 || T.ch[j] == T.ch[k]) {
    			++j;
    			++k;
    			next[j] = k;
    		}
    		else {
    			k = next[k];
    		}
    	}
    }
    void Get_NextVal(HString T, int next[], int nextval[]) {
    	int j = 2, k = 0;
    	Get_Next(T, next);
    	nextval[1] = 0;
    	while (j <= T.len) {
    		k = next[j];
    		if (T.ch[j] == T.ch[k]) {
    			nextval[j] = nextval[k];
    		}
    		else {
    			nextval[j] = next[j];
    		}
    		j++;
    	}
    }
    

    通常,模式串的长度m比主串的长度n小很多,且计算next或者nextval函数的时间复杂度为O(m)。因此,对于整个匹配算法来说,所增加的计算next或nextval时值得的。
    BF算法的时间复杂度为O(m*n),但是实际接近于O(n+m),因此至今仍被采用。KMP算法仅当模式串与主串之间存在许多“部分匹配”的情况下,才会比BF算法快。KMP算法的最大特点就是主串的指针不需要回溯,整个匹配过程中,主串仅需从头到尾扫描一次,对于处理从外设输入的庞大文件很有效,可以边读边匹配。

    四、KMP以及BF的完整代码实现。(Visual Studio 2017开发环境)

    头文件:DString.h

    #pragma once
    #include<windows.h>
    typedef struct {//堆串存储结构
    	char *ch;//若是非空串,则是指向串的起始地址;否则为空
    	int len;//字符串的长度
    }HString;
    //串初始化函数
    void HStrInit(HString *S) {
    	S->ch = NULL;
    	S->len = 0;
    }
    //串赋值函数
    int HStrAssign(HString *S, const char *chars) {
    	int i = 0;
    	if (NULL == chars || NULL == S) {
    		return 0;
    	}
    	else {
    		while (chars[i] != '\0') {
    			i++;
    		}
    		S->len = i;//串S的长度等于串chars的长度
    		if (0 != S->len) {
    			if (S->ch != NULL) {
    				free(S->ch);
    			}
    			S->ch = (char *)malloc(sizeof(char)*(S->len + 1));//0号单元不用,故比实际需求多开辟一个空间
    			if (NULL == S->ch) {//空间开辟失败
    				return 0;
    			}
    			for (i = 1; i <= S->len; i++) {//将chars的内容逐一赋值给S->ch
    				S->ch[i] = chars[i - 1];
    			}
    		}
    		else {
    			S->ch = NULL;//当chars的长度为0时,则置S为空串。
    		}
    		return 1;
    	}
    }
    //打印
    void print(HString *S) {
    	for (int i = 1; i <= S->len; i++) {
    		printf("%c", S->ch[i]);
    	}
    	printf("\n");
    }
    //BF模式匹配算法
    int Index(HString S, int pos, HString T) {
    	int i = pos;//主串从pos开始
    	int j = 1;//模式串从头开始
    	while (i <= S.len&&j <= T.len) {
    		if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
    			i++;
    			j++;
    		}
    		else {//当对应字符不相等时
    			i = i - j + 2;//主串回溯到i-j+2的位置重新比较
    			j = 1;//模式串从头开始重新比较
    		}
    	}
    	if (j > T.len) {//匹配成功时,返回匹配起始位置
    		return i - T.len;
    	}
    	else {//匹配失败,返回0
    		return 0;
    	}
    }
    //统计BF模式匹配算法的比较次数
    int IndexCount(HString S, int pos, HString T) {
    	int i = pos;//主串从pos开始
    	int j = 1;//模式串从头开始
    	int count = 0;
    	while (i <= S.len&&j <= T.len) {
    		if (S.ch[i] == T.ch[j]) {//当对应字符相等时,比较后续字符
    			i++;
    			j++;
    		}
    		else {//当对应字符不相等时
    			i = i - j + 2;//主串回溯到i-j+2的位置重新比较
    			j = 1;//模式串从头开始重新比较
    		}
    		count++;
    	}
    	return count;
    	
    }
    //KMP模式匹配算法
    void Get_Next(HString T, int next[]) {
    	int j = 1, k = 0;
    	next[1] = 0;
    	while (j < T.len) {
    		if (k == 0 || T.ch[j] == T.ch[k]) {
    			++j;
    			++k;
    			next[j] = k;
    		}
    		else {
    			k = next[k];
    		}
    	}
    }
    void Get_NextVal(HString T, int next[], int nextval[]) {
    	int j = 2, k = 0;
    	Get_Next(T, next);
    	nextval[1] = 0;
    	while (j <= T.len) {
    		k = next[j];
    		if (T.ch[j] == T.ch[k]) {
    			nextval[j] = nextval[k];
    		}
    		else {
    			nextval[j] = next[j];
    		}
    		j++;
    	}
    }
    int Index_KMP(HString S, int pos, HString T,int nextval[]) {
    	int i = pos;//主串从第pos开始
    	int j = 1;//模式串从头开始
    	while (i <= S.len&&j <= T.len) {
    		if (j == 0 || S.ch[i] == T.ch[j]) {//继续比较后继字符
    			++i;
    			++j;
    		}
    		else {
    			j = nextval[j];
    		}
    	}
    	if (j > T.len) {//匹配成功
    		return i - T.len;//返回匹配的起始位置
    	}
    	else {
    		return 0;
    	}
    }
    //统计KMP算法的比较次数
    int Index_KMPCount(HString S, int pos, HString T, int nextval[]) {
    	int i = pos;//主串从第pos开始
    	int j = 1;//模式串从头开始
    	int count = 0;
    	while (i <= S.len&&j <= T.len) {
    		if (j == 0 || S.ch[i] == T.ch[j]) {//继续比较后继字符
    			++i;
    			++j;
    		}
    		else {
    			j = nextval[j];
    		}
    		count++;
    	}
    	return count;
    }
    
    

    源文件:

    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include"DString.h"
    int main() {
    	HString S;
    	HString T;
    	HStrInit(&S);
    	HStrInit(&T);
    	char a[] = "aaabaaaab";
    	char b[] = "aaaab";
    	HStrAssign(&S, a);
    	HStrAssign(&T, b);
    	printf("主串:");
    	print(&S);
    	printf("模式串:");
    	print(&T);
    	printf("BF模式匹配:\n");
    	int index = Index(S, 1, T);
    	int count1 = IndexCount(S, 1, T);
    	printf("index=%d\n", index);
    	printf("比较次数:%d\n", count1);
    	printf("KMP模式匹配:\n");
    	int *next,*nextval;
    	next = (int *)malloc(sizeof(int)*(T.len + 1));
    	nextval = (int *)malloc(sizeof(int)*(T.len + 1));
    	Get_NextVal(T,next,nextval);
    	printf("next[]数组如下\n");
    	for (int i = 1; i < (T.len + 1); i++) {
    		printf("%d ", next[i]);
    	}
    	printf("\nnextval[]数组如下:\n");
    	for (int i = 1; i < (T.len + 1); i++) {
    		printf("%d ", nextval[i]);
    	}
    	printf("\n");
    	int index1 = Index_KMP(S, 1, T, next);
    	int count2 = Index_KMPCount(S, 1, T, nextval);
    	printf("index1=%d\n", index1);
    	printf("比较次数:%d\n",count2);
    
    
    
    	system("pause");
    
    
    
    
    
    
    
    
    
    
    
    	return 0;
    }
    

    五、测试结果如下

    在这里插入图片描述

    展开全文
  • 数据结构与算法之模拟匹配算法,最新解法,附代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 229,360
精华内容 91,744
关键字:

模式匹配算法

友情链接: 579571278PCF_dispersion.rar