子串定位

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

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

#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数组求法的整理

传送门