字符串匹配–朴素算法

字符串匹配–朴素算法假设有两个字符串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)


相关推荐

  • 关于Cloneable接口和clone方法「建议收藏」

    关于Cloneable接口和clone方法「建议收藏」1、使用创建对象有两种方式:new和clone当一个对象创建过程复杂,我们是否可以根据已有的对象直接来克隆一份,而不必关系创建的细节呢(原型模式)。1.1JavaObject根类默认提

  • cs模式与bs的区别_BS架构是CS架构的替代品

    cs模式与bs的区别_BS架构是CS架构的替代品C/S:又称Client/Server或客户/服务器模式。客户端需要安装专用的客户端软件。 能充分发挥客户端PC的处理能力,,很多工作可以在客户端处理后再提交给服务器。C/S的主要特点是交互性强、具有安全的存取模式、网络通信量低、响应速度快、利于处理大量数据。但是该结构的程序是针对性开发,变更不够灵活,维护和管理的难度较大。通常只局限于小型局域网,不利于扩展。B/S是Browe

  • .NET .cshtml乱码 代码丢失

    .NET .cshtml乱码 代码丢失见了鬼莫名其妙的代码自己乱码丢了!!!之前有同事说他碰见过这个问题,但是是在电源断电VS没有保存的时候发生的。我这什么都没碰就睡了一觉起来代码丢了解决方案:只能回滚代码发生原因推测:之前架设SVN的时候.CSHTML的文件类型是一个特殊类型,不跟正常的htmlcsjava什么的一样,这次乱码很可能跟vs自己读取这个文件类型的方式有关系。

  • WPF Visifire图表控件使用基础

    WPF Visifire图表控件使用基础https://www.cnblogs.com/wyuan/archive/2012/07/22/WPF.html引言:  由于项目中需要使用Visifire所以自己就写了一些demo,大家一起共享!基础Visifire图表的展示1.Visifire的创建需要引用的DLL包【WPFToolkit.dll;WPFVisifire.Charts;WPFVisifire.Gauges(这个以后会用到)】2

  • EFI shell操作

    EFI shell操作进入EFIshell后,切换盘符使用fs0:(注意冒号不能丢)

  • 圆周率小数点后5000位数值表_输出一位小数C语言

    圆周率小数点后5000位数值表_输出一位小数C语言圆周率2500位圆周率500位3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745…

发表回复

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

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