大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...