字符串模式匹配bf算法_字符串排列组合算法

字符串模式匹配bf算法_字符串排列组合算法字符串匹配【问题描述】对于字符串S和T,若T是S子串,返回T在S中的位置(T的首字符在S中对应的下标),否则返回-1.【问题求解】采用直接穷举法求解,称为BF算法。该算法从S的每一个字符开始查找,看T是否会出现。例如,S=“aababcde”,T=“abcd”:…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

字符串匹配

【问题描述】
对于字符串S和T,若T是S的子串,返回T在S中的位置(T的首字符在S中对应的下标),否则返回-1.

【问题求解】

● ㈠ BF算法

该直接穷举算法从字符串S的每一个字符开始查找,看字符串T是否会出现。
第一步:把T[0] 跟S [0] 匹配,如果相同则匹配下一个字符;
第二步:当出现字符不相同,丢弃前面的已匹配信息 ,T[1] 跟 S[0]匹配,循环进行,直到主串结束,或者出现匹配成功的情况。
例如:S=“aababcde”,T=“abcd”;过程如下:
在这里插入图片描述

【BF算法代码】
#include<stdio.h> 
#include<string.h>
int BF(char s[],char t[])  //字符串匹配
{ 
    int i=0,j=0;
while (i<strlen(s)&&j<strlen(t))
{ 
   
	if(s[i]==t[j]){ 
           //比较两个字符串相同时 
		i++;
		j++;
	}
	else{ 
                     //比较两个字符串不相同时 
		i=i-j+1;           //i回退到原来i的下一个位置 
		j=0;               //j从0开始 
	}
 }
 if(j==strlen(t))          //t的字符比较完毕 
    return i-j;            //t是s的子串,返回位置 
 else                      //t不是s的子串 
    return -1;             //返回-1 
}
int main(){ 
   
	char S[]="abaacababcac";
	char T[]="ababc";
	printf("T在S中出现的起始位置: %d\n",BF(S,T));
}

【程序结果】
在这里插入图片描述
时间复杂度:O(n*m).
算法缺陷:丢弃前面的匹配信息的方法,极大地降低了匹配效率。

● ㈡ KMP算法

定义〗:Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串T 的出现位置。
算法描述〗:

设主串T为:A B A A C A B A B C A C

模式串S为:A B A B C

第一次匹配
设主串T为:A B A A C A B A B C A C

模式串S为:A B A B C

①寻找前缀后缀最长公共元素长度 .
由于T[3]≠S[3],而T[0] ~T[2]相同;则移动找出最长的相同的前缀和后缀并使他们重叠,计算过程和方法如下表格所示:
在这里插入图片描述
[程序思想举例]
<1>.leni为用来比较的变量,pattern[i] == pattern[len],len++,prefix[i]=len的值,prefix[i] = len的值,i继续向下比较。
在这里插入图片描述
<2>.当pattern[i] ≠pattern[len]时,且len>0的情况下,向左逐次移动,再次进行循环比较,可计算得A代表的公共长度为1;直至结束即可
在这里插入图片描述

【算法代码①】
:prefix_table(前缀后缀最长公共元素长度表)

void prefix_table(char pattern[],int prefix[],int n){ 
    //1.要匹配的子串表,2.前缀表,3.表长 
	 prefix[0] = 0;	            //定义第一个字符最长公共长度为0;
	 int len = 0;               //用来比较的长度
	 int i   = 1;
	 while(i<n){ 
   
	 	if(pattern[i] == pattern[len]){ 
   
	 		len++;
	 		prefix[i] = len;
	 		i++;
		 }else{ 
                             //当pattern[i]≠pattern[len]时
		 	if(len > 0){ 
                     //避免向左校对时出界
		 		len = prefix[len - 1];    
		 }else{ 
                              
		 	prefix[i]=len;
		 	i++;
		 }
	   }
    } 
}

【程序结果】
在这里插入图片描述

②求next数组.
next 数组考虑的是除当前字符外的最长相同前缀后缀,所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第①步骤中求得的值整体右移一位,然后初值赋为-1,如下表格所示:
在这里插入图片描述
【算法代码②】
:Next(前缀移动方法)

void Next(int prefix[],int n){ 
     //前缀表移动 
	int i;
	for(i=n-1;i>0;i--){ 
   
		prefix[i]=prefix[i-1];
	}
	prefix[0]=-1;
}

【程序结果】
在这里插入图片描述

③根据next数组继续进行匹配.
<1>. 根据第一次匹配分析,当T[3]≠S[3],字符B对应的Next值=1,即移动S子串,S[1]移动于T[3]下,继续进行匹配;
在这里插入图片描述
<2>.当S[1]≠T[4]时,字符B对应的Next值=0,即将S[0]移动于T[4]下匹配;
<3>.当S[0]≠T[4]时,字符A对应的Next值=-1,即将虚拟的S[-1]向右移一位至T[4]下,等价于S[0]移动于T[5]下匹配;
<4>.匹配成功,继续寻找;匹配成功的最后一位字符C对应的Next值=2,把对应的S[2]移动于T[9]下匹配;
<5>.匹配结束;返回子串对应的起始位置:5。
匹配过程和方法表如下:
在这里插入图片描述

【KMP算法代码】

注==:完整算法代码

#include<stdio.h>
#include<malloc.h>
#include<string.h>
void prefix_table(char pattern[],int prefix[],int n){ 
    //1.要匹配的子串表,2.前缀表,3.表长 
	 prefix[0] = 0;	   //定义第一个字符最长公共长度为0; 
	 int len = 0;      //用来比较的长度
	 int i   = 1;
	 while(i<n){ 
   
	 	if(pattern[i] == pattern[len]){ 
   
	 		len++;
	 		prefix[i] = len;
	 		i++;
		 }else{ 
   
		 	if(len > 0){ 
                   //避免向左校对时出界
		 		len = prefix[len - 1];  //当pattern[i]≠pattern[len]时
		 }else{ 
   
		 	prefix[i]=len;
		 	i++;
		 }
	   }
    } 
}

void Next(int prefix[],int n){ 
     //前缀表移动 
	int i;
	for(i=n-1;i>0;i--){ 
   
		prefix[i]=prefix[i-1];
	}
	prefix[0]=-1;
}

void kmp_search(char text[],char pattern[]) { 
     //text为母表,patter为子表
	int n=strlen(pattern);
	int m=strlen(text);
	int* prefix=(int*)malloc(sizeof(int)*n);  //创建数组
	prefix_table(pattern,prefix,n);
	Next(prefix,n);
	
	//text[i] 定位表示 len(text) =m
	//pattern[j], 定位表示len(pattern )= n 
	int i=0;
	int j=0;
	while(i<m){ 
   
		if(j == n-1 && text[i] == pattern[j]){ 
   
			printf("子串匹配于母串起始位置: %d\n",i-j);
			j=prefix[j];
		}
		if(text[i] == pattern[j]){ 
   
			i++;
			j++;
		}else{ 
   
			j=prefix[j];
			if(j==-1){ 
   
				i++;
				j++;
			}
		}
	}
}

int main(){ 
   
	char pattern[]="ABABC";
	char text[]   ="ABAACABABCAC";
	kmp_search (text,pattern);
	return 0;
} 

【算法结果】
在这里插入图片描述
时间复杂度:O(n+m).

假如李白会编程,夸张字符随意配;暴力美学最简易,KMP经典最美丽。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/171704.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • android studio报错Gradle project sync failed. Please fix your project and try again

    android studio报错Gradle project sync failed. Please fix your project and try againAndroidStudio导入项目或者新建项目想运行的时候可能会报错Gradleprojectsyncfailed.Pleasefixyourprojectandtryagain,原因应该是Gradle的一些东西没配好。这2个版本必须要保证本地有,而且一定要对得上。怎么知道本地有没有,下面2张图片展示他们各自的路径。(默认路径在安装AndroidS…

  • 开启新篇章——软工视频总结

    开启新篇章——软工视频总结开启新篇章——软工视频总结

  • iconfont的基本使用

    iconfont的基本使用阿里巴巴的iconfont网站有很多小图标可供我们使用,链接如下iconfont网站链接。这个图标资源库可以一个图片一个图片的下载,也支持批量下载。下面我来介绍下批量下载。进入网页之后,可以选择自己需要的小图标,将鼠标移动到小图标上之后,就会出现如下所示的3个按钮。这3个按钮分别是添加到购物车、收藏、下载的按钮。如果需要批量下载图片,我们可以先添加到购物车。加入购物车之后,点击购物车按钮就会在右侧出现一个弹框。点击添加到项目(添加到项目,可以根据自己的需要设置下载哪些选项)

    2022年10月25日
  • 缓存穿透,缓存击穿,缓存雪崩解决方案分析[通俗易懂]

    缓存穿透,缓存击穿,缓存雪崩解决方案分析[通俗易懂]前言设计一个缓存系统,不得不要考虑的问题就是:缓存穿透、缓存击穿与失效时的雪崩效应。缓存穿透缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时被动写的,并且出于容错考虑,如果从存储层查不到数据则不写入缓存,这将导致这个存在的数据每次请求都要到存储层去查询,失去了缓存的意义。在流量大时,可能DB就挂掉了,要是有人利用不存在的key频繁攻击我们的应用,这就是漏洞。解决方案

  • 架设ftp服务器从入门到精通[通俗易懂]

    架设ftp服务器从入门到精通[通俗易懂]1.FTP是什么FTP的全称是FileTransferProtocol(文件传输协议)。顾名思义,就是专门用来传输文件的协议。FTP服务器则是在互联网上提供存储空间的计算机,它们依照FTP协议提供服务。当它们运行时,用户就可以连接到服务器上下载文件,也可以将自己的文件上传到FTP服务器中。有时把FTP服务器简称为FTP。FTP服务器的存在,大大方便了网友之间远程交换文件资料的需要,充分体现了互联网资源共享的精神。现在许多朋友都已经用上了宽带网,而且硬盘也有足够的空间,完全可以通过软件手段把自己的

  • ctf-web:文件包含漏洞和举例-HCTF2018 WarmUp「建议收藏」

    ctf-web:文件包含漏洞和举例-HCTF2018 WarmUp「建议收藏」我又回来更新了,这次是关于web方面的文件包含漏洞.我会在后面以详细的角度来写清楚这个漏洞的利用方法.当然,以下都是我自己的理解,表述什么的都有些野人化了.所以希望各位大佬手下留情.一.漏洞产生的原因这个漏洞可以追溯到很久.更准确来说,其实是人为产生的.由于我php学的不是很专业,所以我就拿c语言来举例了.php里面使用的是include命令,c语言使用的是#include预处理命令.作用是相似的.我新建了两个文件,内容如图.wzc.h:#include”stdio.h”voidpri.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号