kmp算法

data_structure

一、kmp算法的核心思想

KMP算法的想法是，设法利用某些已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

二、具体实现

具体的算法实现不说了，书上都有，很详细。
下面贴上做了对于长连续串next数组的优化的代码

int kmp(const char *src,const char *dst)
{
    int i=0;//记录源串信息
    int j=0;//记录子串信息
    int n=strlen(src);
    int m=strlen(dst);
    //next数组存的是，如果匹配失败，j回到next[j]，i不变，继续比较、
    while(i<n && j<m)//当字符没有到底，进行比较
    {
        if (j==-1 || src[i]==dst[j])//如果当前字符相等，后移继续比较，若不等，取next数组中值，开始比较
        {
            i++; j++;
        }
        else
            j=next[j];
    }
    if (j>=m)
        return i-m; //返回
    else
        return -1;  //没有找到
}
void GetNext(const char *str)
{
    int m=strlen(str);
    int j=0;int k=-1;
    next[0]=-1;
    while (j<m-1)
    {
        //以前一种符合的状态为基准，判断现在的状态，如果继续符合，值加1，否则回到之前从比
        if(k==-1||str[j]==str[k])//如果刚进来，则k++，并把值存入next数组。
        {
            j++;  k++;
            next[j] = k;
            if (str[j]==str[k])
                next[j] = next[k];
        }
        else
            k=next[k];  //回到之前。
    }
}

三、测试

测试一下：

int main()
{
    char str[20]="aaaabcdabcda";
    char a[10]="abc";
    cout<<str<<endl<<a<<endl;
    GetNext(a);
    cout<<kmp(str,a)<<endl;
    char str1[20]="abcdabcda";
    char a1[10]="aaaabc";
    cout<<str1<<endl<<a1<<endl;
    GetNext(a1);
    cout<<kmp(str,a1)<<endl;
    return 0;
}

结果：