字符串匹配

s

#include<bits/stdc++.h>
using namespace std;

//暴力算法 这里的字符串初始为0
// 主串有可能回退 最差O(nm)
int BL(string a, string b)
{
    int i=1,j=1;// 双指针指向这两个数组的匹配位置
    while(i<a.size() && j<b.size())
    {
        if(a[i]==b[j])// 该位置匹配成功
        {
            // cout << a[i] <<" " << b[j]<< "\n";
            i++,j++;
        }else{ // 匹配不成功 i相对上次后移一位 j回到初始位置
        
            i = i - j + 2;//i每次都增加1
            j = 1;
            // cout << i <<" "<< j <<"\n";
        }
    }
    // 如果退出循环 就说明有一个遍历完所有元素了 
    if(j==b.size())
    {
        return i - j + 1 ;
    }
    return -1;   
}

int nex[100];

void get_next(string s)
{
    int i = 1,j = 0;
    
    nex[1] = 0;
    while(i<s.size())
    {
        if(j==0 || s[i]==s[j])
        {
            i++,j++;
            nex[i] = j;
        }else{
            j = nex[j];
        }
    }
}

// 主串不会发生回退 O(n+m)
int KMP(string a,string b)
{
    get_next(b);
    for(int i = 1;i<=b.size();i++)
    {
        cout << nex[i] <<" ";
    }
    
    int i = 1, j = 1;
    for(;i<a.size() && j<b.size();)
    {
        if(j == 0 || a[i]==b[j])// 当前字符匹配成功 这里的j==0意思为全部匹配失败 没有元素与当前一致
        {
            cout << i <<" " << j <<" "<< a[i] <<" "<<b[j] <<"\n";
            i++,j++;
        }else{
            j = nex[j];
            cout <<"进行修改"<< i <<" "<< j <<"\n";
        }
        
    }
    
    if(j>=b.size())
    {
        return i-b.size()+1;
    }
    return -1;
}


int main()
{
    string a,b;
    //手动调节 从一开始
    // 因为这里调节了 所有后面有些尴尬 他的字符串的实际长度和
    //计算的结果不一致 需要注意一下
    a = "0ababcabcacbab";
    b = "0abcac";
    // cout << a << b;
    // int bl = BL(a,b); 
    cout << KMP(a,b);
    // cout << bl;
    return 0;
}

上面主要写了KMP的算法,KMP的主要思想就是先求出next数组,这个数组的作用是当主串与子串匹配失败时,将子串的指针修改成next的值,这样也就避免主串回溯了,保证了效率