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.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/171715.html原文链接：https://javaforall.net
