简介

KMP算法属于字符串匹配算法，这次先简单看看吧，代码实现比较复杂,算法思想是dp
该教程是在 text 里匹配 pattern

视频教程

• 理论篇

• 实操篇

代码分析

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


void prefix_table(char pattern[], int prefix[], int n){
    prefix[0] = 0;
    int len = 0;
    int i = 1;
    while(i < n){
        if(pattern[i] == pattern[len]){
            len++;
            prefix[i] = len;
            i++;
        }else{
            if(len > 0){
                len = prefix[len - 1];
            }else{
                prefix[i] = len;
                i++; 
            }

        }

    }
}

void move_prefix_table(int prefix[], int n){
    for(int i = n - 1; i > 0; i--){
        prefix[i] = prefix[i - 1];
    }
    prefix[0] = -1;
}

void kmp_serach(char text[], char pattern[]){
    int n = strlen(pattern);
    int* prefix = new int[n];
    prefix_table(pattern, prefix, n);
    move_prefix_table(prefix, n);

    // define
    // text[i]  , len(text) = m
    // pattern[j]   , len(pattern) = n

    int i = 0;
    int j = 0;
    int m = strlen(text);

    while(i < m){
        
        if(j == n - 1 && text[i] == pattern[j]){
            cout << "Found pattern at " << i - j << endl;
            j = prefix[j];
        }        

        if(text[i] == pattern[j]){
            i++; j++;
        }else{
            j = prefix[j];
            if(j == -1){
                i++; j++;
            }
        }

    }
}

int main(){

    char pattern[] = "ABABCABAA";
    char text[] = "ABABABCABAABABABAB";
    /*
    int prefix[9];
    int n = 9;

    prefix_table(pattern, prefix, n);
    move_prefix_table(prefix, n);
    
    for(int i = 0; i < n; i++){
        cout<< prefix[i] << " ";
    }
    */
    kmp_serach(text, pattern);

    return 0;
}