子串定位

March 25, 2020 数据结构 访问: 25 次

朴素贝叶斯算法(朴素算法)

当遇到不一样的字符时,利用回溯,然后移动一位,重新开始比较,程序如下:

#include<iostream>
#include<string>
using namespace std;
int BF(string M,string T,int pos)
{
    int i=pos;
    int j=0;
    int Mlen=M.length();
    int Tlen=T.length();

    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;
}

KMP算法

kmp算法相对于朴素算法而言是比较快的

kmp算法采用的是当遇到不同的字符时,不回溯,而是将模式进行右移

规律

通过上面的方式,先找出来模式的next数组,然后进行子串查询

  • 当第一个字符不相等时,则一号位与主串的下一位进行比较(也就是说,当最长相等前后缀为0时,则一号位与主串的下一位进行比较)
  • 当最长相等前后缀为n时(且n应当小于指针前的长度),则模式串 串的n+1号位置与主串指针相比较

关于KMP算法中next数组和nextVal数组求法的整理

传送门

添加新评论