[数据结构与算法]【数据结构学习】KMP匹配方法实现

代码展示

#include<cstring>
#include<iostream>
using namespace std;

//目标向量值计算函数
int* move(string a,int* mov)
{
    int len=a.length();
    mov[0]=0;
    for(int k,i=1;i<len;i++)
    {
        k=mov[i-1];
        while(k>0&&a[k]!=a[i])
        {
            k=mov[k-1];
        }
        if(a[k]==a[i])mov[i]=k+1;
        else mov[i]=0;
    };
    cout<<"The target vector value is:"<<endl;
    for(int i=0;i<len;i++)cout<<mov[i]<<" ";
    cout<<endl;
    return mov;
};

//Search匹配函数
int Search(string t,string s,int* KMP)
{
    int i=0,j=0,len_t=t.length(),len_s=s.length();
    while(i<len_t&&j<len_s)
    {
        if(t[i]==s[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-KMP[i-1];
        }
    }
    if(i>=len_t)return (j-len_t);
    else return -1;
}

//主函数
int main()
{
    string Target;
    string Source="cococola";
    cout<<"Please enter the Target:"<<endl;
    cin>>Target;
    int len=Target.length();
    int mov[len];
    move(Target,mov);
    int i=Search(Target,Source,mov);
    if(i!=-1)cout<<"The same string's position is "<<i<<endl;
    else cout<<"The same string was not found."<<endl;
    return 0;
}

小结

与传统穷举法匹配相比，节省了一部分指针回溯的时间，降低了时间复杂度。

巧妙之处便在于特征向量组。它确定了Target每个元素在匹配错误后，指针应该偏移的量。

特征向量组的定义利用递归定义，从0号元素开始，初始值为0。在已知i-1 号元素特征向量值为K的情况下，只需确定i 号元素与K号元素是否仍然相同。若相同则i 号元素的特征值为K+1，反之则取较小的K2继续进行上述比较。如此不断递归往复，便可得到特征向量组。