考研数据结构之KMP算法

一、KMP算法

kmp算法

1.KMP算法解决的问题
KMP算法解决了在朴素模式匹配算法中，匹配串指针回溯导致匹配效率低的问题。
2.朴素模式匹配算法

#include<stdio.h>

/**
 * 朴素模式匹配. 
 * @param pattern 匹配字符串.
 * @param string 目标字符串. 
 * @return 找到返回位置，否则返回-1. 
 */ 
int findPatternStringPosition(char* pattern, char* string);

int main() {
    char* pattern = "musk";
    char* string = "maxwellmusikmusk";
    int position = findPatternStringPosition(pattern,string);
    printf("position = %d",position); 
    
}
int findPatternStringPosition(char* pattern, char* string) {
    int position = -1;
    int count = 0; 
    // 主串指针 
    char* mainStrPointer = string;
    // 模式串指针 
    char* patternPointer = pattern;
    // 辅助指针. 
    char* ptr = mainStrPointer;
    while(*mainStrPointer) {
        if(*ptr == *patternPointer) {
            ptr++;
            patternPointer++;   
        }
        else{
            count++;
            mainStrPointer++;
            ptr = mainStrPointer;
            patternPointer = pattern; 
        }
        if(!*patternPointer){
            position = count;
            break;
        }
    }
    return position;
}

3.KMP算法

#include <stdio.h>
#include <string.h>

void Next(char*T,int *next){
    int i=1;
    next[1]=0;
    int j=0;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}

int KMP(char * S,char * T){
    int next[10];
    Next(T,next);
    int i=1;
    int j=1;
    while (i<=strlen(S) && j<=strlen(T)) {
        if (j==0 || S[i-1]==T[j-1]) {
            i++;
            j++;
        }
        else{
            // i不回溯，j回溯. 
            j=next[j];
        }
    }
    if (j>strlen(T)) {
        return i-(int)strlen(T);
    }
    return -1;
}

int main() {
    int i=KMP("ababcabcacbab","abcac");
    printf("%d",i);
    return 0;
}

二、对KMP算法继续优化

对next数组的优化.

void Next(char*T,int *next){
    int i=1;
    next[1]=0;
    int j=0;
    while (i<strlen(T)) {
        if (j==0||T[i-1]==T[j-1]) {
            i++;
            j++;
            if (T[i-1]!=T[j-1]) {
               next[i]=j;
            }
            else{
                next[i]=next[j];
            }
        }else{
            j=next[j];
        }
    }
}

文章参考：http://data.biancheng.net/view/13.html

三、代码解析：

待更新...