kmp算法实现

下面是kmp算法的具体实现

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

using namespace std;


int* nextArray(const char* pattern, int m) {
    int* next = new int[m];
    next[0] = -1;
    int j = 0;
    int k = -1;
    while (j < m - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    return next;
}

int* nextValueArray(const char* pattern, int m) {
    int* nextVal = new int[m];
    nextVal[0] = -1;
    int j = 0;
    int k = -1;
    while (j < m - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            if (pattern[j] != pattern[k]) {
                nextVal[j] = k;
            } else {
                nextVal[j] = nextVal[k];
            }
        } else {
            k = nextVal[k];
        }
    }
    return nextVal;
}

int KMP(const char* text, const char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    int* next = nextArray(pattern, m);
    int i = 0;
    int j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    delete[] next;
    if (j == m) {
        return i - j; // 匹配成功，返回起始位置
    } else {
        return -1; // 匹配失败
    }
}


int main() {
    const char* text = "ababcabcacbab";
    const char* pattern = "abcac";
    int position = KMP(text, pattern);
    if (position != -1) {
        cout << "Pattern found at index: " << position << endl;
    } else {
        cout << "Pattern not found." << endl;
    }
    return 0;
}