KMP算法实现及应用

1、KMP算法实现问题：

KMP算法实现就是字符查找问题，假设现在有这样一个问题，有一个文本串S和一个模式串P，要查找P在S中的位置，即从文本串S中找出模式串P第一次出现的位置。

问题分析：

假设文本串长度为n，模式串长度为m。

（1）暴力求解算法下，当两者匹配S[i] = P[j] 时，i++,j++；当不匹配时，i++,j=0。也就是说每次匹配失败时，模式串相对于文本串向右移动了一位。

时间复杂度为O(m*n)，空间复杂度为O(1)。

（2）KMP算法下，当两者匹配S[i] = P[j] 时，i++,j++；当不匹配时，j = next[j]（next[j] <= j-1）。也就是说每次匹配失败时，模式串相对于文本串向右至少移动一位，移动位数为j - next[j] >= 1。时间复杂度为O(m+n)，空间复杂度为O(m)。

在实现KMP算法之前，必须获取模式串P的next数组，设next[j]=k，即模式串前j-1位有k前缀和k后缀相等。

获取模式串next数组程序实现：

void GetNext(char* p,int next[]){
    int plen = strlen(p);
    int k = -1;
    next[0] = -1;
    int j;
    //此时，k表示next[j-1]，p[j]表示后缀，p[k]表示前缀
    //k=-1表示未找到前缀后缀相等的情况，首次可先忽略
    while(j < plen -1){
        if(k ==-1 || p[j] == p[k]){
            k++;
            j++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}

运行结果： 对于模式串 abaabcabc的next数组为：

这里对next数组进行了改进，在原始的next数组中，当next[j] = k, p[j] = p[k]时，next[j] 可以直接等于next[k]。这样做的好处就是在KMP最差情况下，即模式串首字符与其他字符都相等的时候，时间复杂度能够提高，但还是在一个数量级。

改进next数组代码实现：

void GetNext1(char* p,int next[]){
    int plen = strlen(p);
    int k = -1;
    next[0] = -1;
    int j;
    //此时，k表示next[j-1]，p[j]表示后缀，p[k]表示前缀
    //k=-1表示未找到前缀后缀相等的情况，首次可先忽略
    while(j < plen -1){
        if(k ==-1 || p[j] == p[k]){
            k++;
            j++;
            if(p[j] == p[k])//当前缀与后缀再次相等时，直接替换成next[k]
                next[j] = next[k];
            else
                next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}

运行结果：改进后next数组为：

在获取模式串next数组后，就可以进行KMP算法，进行字符串的查找。

程序实现如下：

/***************************************
FileName KMPCode.cpp
Author : godfrey
CreatedTime : 2016/5/8
****************************************/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

void GetNext(char* p,int next[]){
    int plen = strlen(p);
    int k = -1;
    next[0] = -1;
    int j;
    //此时，k表示next[j-1]，p[j]表示后缀，p[k]表示前缀
    //k=-1表示未找到前缀后缀相等的情况，首次可先忽略
    while(j < plen -1){
        if(k ==-1 || p[j] == p[k]){
            k++;
            j++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}

void GetNext1(char* p,int next[]){
    int plen = strlen(p);
    int k = -1;
    next[0] = -1;
    int j;
    //此时，k表示next[j-1]，p[j]表示后缀，p[k]表示前缀
    //k=-1表示未找到前缀后缀相等的情况，首次可先忽略
    while(j < plen -1){
        if(k ==-1 || p[j] == p[k]){
            k++;
            j++;
            if(p[j] == p[k])//当前缀与后缀再次相等时，直接替换成next[k]
                next[j] = next[k];
            else
                next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}

int KMPCode(char* s,char* p,int p_next[]){
    int result = -1;
    int plen = strlen(p);
    int slen = strlen(s);
    int i=0;
    int j=0;
    while(i < slen){
        if(j == -1 || s[i] == p[j]){
            i++;
            j++;
        }
        else{
            j = p_next[j];
        }

        if(j == plen){
            result = i - plen;
            break;
        }
    }
    return result;
}
int main()
{
    char s[1024],p[1024];
    int next[1025];
    int num;
    while(cin>>s>>p){
        //GetNext(p,next);
        GetNext1(p,next);
        int plen = strlen(p);
        cout<<"p[i] "<<"next[i] "<<endl;
        for(int i=0;i<plen;i++){
            cout<<p[i]<<"    "<<next[i]<<endl;
        }
        cout<<endl;
        num = KMPCode(s,p,next);
        if(num == -1){
            cout<<"Not found "<< p <<" in " << s <<endl;
        }
        else{
            cout<< "Found " << p << " in " << s << " at " <<num<<endl;
        }
    }
    return 0;
}

运行结果：

2、KMP算法应用问题

给定一个长度为n的字符串S，如果存在一个字符串P，重复若干次后P能够得到S，那么S叫做周期串，P叫做S的一个周期。

如：字符串abcabcabc为周期串，abc，abcabc是它的周期，其中abc是最小周期。设计算法，计算S的最小周期大小，如果不存在最小周期，返回-1。

问题分析：

计算S的next数组，这里求解的是原始的next数组。记last = next[n-1], p = n - 1 -last；如果n%p = 0，则p就是最小周期长度，前p个字符就是最小周期。自己可以画图理解一下，还是比较好理解的。

程序实现：

/***************************************
FileName StringMinPeriod.cpp
Author : godfrey
CreatedTime : 2016/5/8
****************************************/
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int StringMinPeriod(char* p){
    int plen = strlen(p);
    if(plen == 0)
        return -1;
    int* next = new int[plen];
    int k = -1;
    next[0] = -1;
    int j = 0;
    while(j < plen -1){
        if((k ==-1) || (p[j] == p[k])){
            k++;
            j++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }

    next[0] = 0;//将首位恢复为逻辑上的零
    int last = next[plen-1];
    if(last == 0)
        return -1;
    if(plen % (plen - last - 1) == 0)
        return plen - last - 1;
    delete[] next;
    return -1;
}

int main()
{
    char s[1024];
    int MinPeriod;
    while(cin>>s){
        MinPeriod = StringMinPeriod(s);
        cout<<"the string MinPeriod : " <<MinPeriod<<"   ";
        for(int i=0;i<MinPeriod;i++)
            cout<<s[i];
        cout<<endl;
    }
    return 0;
}

运行结果：

转载请注明出处：

C++博客园：godfrey_88

http://www.cnblogs.com/gaobaoru-articles/