字符串匹配–朴素算法

字符串匹配–朴素算法假设有两个字符串M="abcdefabcdx";T="abcdx";想要找到T串在M串中的位置,要怎么找呢?通过画图来看比较过程:也就是说,从主串M的第一个字符开始分别与子串从开头进行比较,当发现不匹配时,主串回到这一轮开始的下一个字符,子串从头开始比较。直到子串所有的字符都匹配,返回所在主串中的下标。写出代码:#include<iostream>#include<string…

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

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

假设有两个字符串

M=”abcdefabcdx”;

T=”abcdx”;

想要找到T串在M串中的位置,要怎么找呢?

通过画图来看比较过程:

字符串匹配--朴素算法

也就是说,从主串M的第一个字符开始分别与子串从开头进行比较,当发现不匹配时,主串回到这一轮开始的下一个字符,子串从头开始比较。直到子串所有的字符都匹配,返回所在主串中的下标。

写出代码:

#include<iostream>
#include<string>
using namespace std;
//从pos位置开始,返回子串在主串中的位置
int BF(string M,string T,int pos)
{
	int i=pos;
	int j=0;
	int Mlen=M.length();//主串的范围[0,Slen)
	int Tlen=T.length();//子串的范围[0,Tlen)

	if(pos<0 && pos>Mlen)
		return -1;

	while(i<Mlen && j<Tlen)
	{
		if(M[i]==T[j])
		{
			++i;
			++j;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(j>=Tlen)
		return i-Tlen;
	else 
		return -1;
}
int main()
{
	string M="abcdefabcdx";
	string T="abcdx";
	cout<<BF(M,T,1)<<endl;
	return 0;
}

分析:

最好情况:一开始匹配成功,M=”abcdfhieabc”,T=”abcdf”;时间复杂度为O(1).

最坏情况:每次不成功都发生在最后一个字符的匹配中,如M=”aaaaaaaaaaaaaaaaaaaaaab”;T=”aaaaaaaab”;假设M长度为m,T长度为n,则需要比较(m-n+1)*n,时间复杂度为O(m-n+1)*n.

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

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

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

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

(0)
blank

相关推荐

  • SpringBoot连接使用PostgreSql数据库

    SpringBoot连接使用PostgreSql数据库目录一、介绍1、情况说明2、安装软件及依赖包二、配置连接数据库其他情况一、介绍1、情况说明在这里我使用SpringBoot配置Mybaits连接到PostgreSql数据库的。我的源码也会提供给大家(此文末尾),效果如下数据库:运行效果:2、安装软件及依赖包完整搭建SpringBoot及依赖包:https://blog.csdn.net…

  • C# 发送Http请求 – WebClient类

    WebClient位于System.Net命名空间下,通过这个类可以方便的创建Http请求并获取返回内容。一、用法1- DownloadData二、用法2- OpenRea

    2021年12月27日
  • idea2021.3.3激活码获取【2021最新】

    (idea2021.3.3激活码获取)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~AERNFLMXDO-eyJsaWNlb…

  • 添加打印机时错误为0x0000011b_连接打印机0x000003e3

    添加打印机时错误为0x0000011b_连接打印机0x000003e3问题描述前几天共享打印机还可以使用的突然就不能打印了,删除重新安装时就提示windows无法连接到打印机,如下图:解决方案这是的补丁代号为KB5005569/KB5005573/KB5005568/KB5005566/KB5005565造成的。卸掉上述补丁即可解决问题步骤找到设置——>更新和安全—->Windows更新—->“查看更新历史记录—->卸载更新本人的经验分享,希望可以帮助到你们,如何不对的地方,可以评论留言,帮我指正一下,如果帮助了你

  • 博客园h1h2h3笔记和文章写作规范

    博客园h1h2h3笔记和文章写作规范为什么要整理?2016-06-16之前写的大多数文章使用的标题都是h3,h4,而并不是h1,h2,h3。在为文章生成目录后有以下问题:1.文章大纲不清晰;2.由于h2h3没有规划好,生成出来

  • acwing-2326. 王者之剑(最小割之最大点权独立集)「建议收藏」

    acwing-2326. 王者之剑(最小割之最大点权独立集)「建议收藏」给出一个 n×m 网格,每个格子上有一个价值 vi,j 的宝石。Amber 可以自己决定起点,开始时刻为第 0 秒。以下操作,在每秒内按顺序执行。若第 i 秒开始时,Amber 在 (x,y),则 Amber 可以拿走 (x,y) 上的宝石。在偶数秒时(i 为偶数),则 Amber 周围 4 格的宝石将会消失。若第 i 秒开始时,Amber 在 (x,y),则在第 (i+1) 秒开始前,Amber 可以马上移动到相邻的格子 (x+1,y),(x−1,y),(x,y+1),(x,y−1) 或原地不动

发表回复

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

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