KMP算法

浏览数：83 / 时间：2015年06月08日

对于KMP算法，最重要的是要把握其中的next数组的含义及求法

考虑一个模式字符串：b1b2...bn，定义next[s]如下：

next[s] is the longest proper prefix of b1b2...bs that is also a suffix of b1b2...bs

#include<iostream>
#include<string.h>
using namespace std;
void makeNext(char *s, int *next){
    int len = strlen(s);
    int j = 0;
    for(int i = 1; i < len; i++){
       while(j > 0 && s[j + 1 - 1] != s[i + 1 - 1])
           j = next[j];
       if(s[j + 1 - 1] == s[i + 1 - 1]){
            j += 1;
            next[i + 1] = j;
        }
        else
           next[i + 1] = 0;
    }
}
int main(){
    char src[] = "ababaa";
    char src1[] = "abababaab";
    char src2[] = "aaaaaa";
    char src3[] = "abbaabb";
    int *next, *next1, *next2, *next3;
    next = new int[strlen(src) + 1];
    memset(next, 0, (strlen(src) + 1) * sizeof(int));
    makeNext(src, next);
    next1 = new int[strlen(src1) + 1];
    memset(next1, 0, (strlen(src1) + 1) * sizeof(int));
    makeNext(src1, next1);
    next2 = new int[strlen(src2) + 1];
    memset(next2, 0, (strlen(src2) + 1) * sizeof(int));
    makeNext(src2, next2);
    next3 = new int[strlen(src3) + 1];
    memset(next3, 0, (strlen(src3) + 1) * sizeof(int));
    makeNext(src3, next3);
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

KMP算法