编写一个kmp.cpp，实现顺序串的kmp算法；编写sqstring.cpp，定义顺序串的结构，并实现顺序串

编写一个kmp.cpp，实现顺序串的kmp算法：

#include <iostream>
#include <cstring>

using namespace std;

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

int kmpSearch(const char *text, const char *pattern) {
    int len1 = strlen(text);
    int len2 = strlen(pattern);
    int *next = new int[len2];
    getNext(pattern, next);

    int i = 0, j = 0;
    while (i < len1 && j < len2) {
        if (j == -1 || text[i] == pattern[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    delete[] next;

    if (j == len2) {
        return i - j;
    } else {
        return -1;
    }
}

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

编写sqstring.cpp，定义顺序串的结构，并实现顺序串：

#include <iostream>

using namespace std;

const int MAX_SIZE = 10001;

struct SqString {
    char data[MAX_SIZE];
    int length;
};

void initSqString(SqString &str, const char *text) {
    int len = strlen(text);
    for (int i = 0; i < len; ++i) {
        str.data[i] = text[i];
    }
    str.length = len;
}

void printSqString(const SqString &str) {
    for (int i = 0; i < str.length; ++i) {
        cout << str.data[i];
    }
    cout << endl;
}

int main() {
    SqString str;
    const char *text = "Hello, world!";
    initSqString(str, text);
    printSqString(str);
    return 0;
}

使用g++编译上述两个文件：

g++ kmp.cpp -o kmp
g++ sqstring.cpp -o sqstring

运行kmp程序，输出为：

Pattern found at index 6

运行sqstring程序，输出为：

Hello, world!