首页 > 代码库 > kmp算法

kmp算法

2024-10-19 18:44:39   209人阅读

    KMP的精髓就在于，用了一个线性的算法，得到了每次在pattern[ j ]发生失配时，应该让pattern往后移动多少步，这个值对应于pattern [0, j - 1]的最长相等{前缀、后缀}的长度。这些值所存的数组叫做next数组。

关键是在于了解next数组的构成。

    对于我自个儿来说，看一下下面这个求next的小例子就可以知道是怎样做了。

    pattern: ABCDABD

    next[]: 0,0,0,0,1,2,0

代码如下：

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

void nextFun(char* str, int* next) {
    next[0] = 0;
    int k = 0;
    int len = strlen(str);
    for (int i = 1; i < len; i++) {
        while (k > 0 && str[k] != str[i])
            k = next[k - 1];
        if (str[i] == str[k]) {
            k++;
        }
        next[i] = k;
    }
}

int KMP(char* str, char* pattern, int* next) {
    int res = 0;
    int len = strlen(str), lenPat = strlen(pattern);
    int k = 0;
    for (int i = 0; i < len; i++) {
        while (k > 0 && str[i] != pattern[k])
            k = next[k - 1];
        if (str[i] == pattern[k])
            k++;
        if (k == lenPat) {
            res++;
            cout << "the matching pattern is shifting "<<i-lenPat+1<<endl;
            k = next[k-1];
        }
    }
    return res;
}

 

kmp算法


联系
我们