前言

ChatGPT 官方暂停了升级 GPT-4 的入口，但目前官网还可以直接升级。请注意，这种升级情况可能会变化（截至2024.8月，此途径仍然可用）。

目前已成功，已经玩了几天了，GPT 4 的插件能力真的强！

参考链接： 2024GPT4.0升级详细指南

Chatgpt4.0 写改进版KMP算法

KMP（Knuth-Morris-Pratt）算法是一种字符串搜索算法，用于在一个主字符串中查找一个模式字符串的出现位置。KMP算法的关键在于利用部分匹配表（也称为前缀函数），避免在匹配失败时的重复计算，从而提高效率。

下面是一个改进版KMP算法的C++实现。改进之处主要在于代码的结构和清晰度，以便于理解和维护。

#include <iostream>
#include <vector>
#include <string>

// 计算部分匹配表（前缀函数）
std::vector<int> computeLPSArray(const std::string& pattern) {
    int m = pattern.size();
    std::vector<int> lps(m, 0);
    int len = 0; // length of the previous longest prefix suffix
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}

// KMP字符串搜索算法
std::vector<int> KMPSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> lps = computeLPSArray(pattern);
    std::vector<int> matches;
    int n = text.size();
    int m = pattern.size();
    int i = 0; // index for text
    int j = 0; // index for pattern

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            matches.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    return matches;
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";

    std::vector<int> result = KMPSearch(text, pattern);

    std::cout << "Pattern found at positions: ";
    for (int pos : result) {
        std::cout << pos << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码解释

1. computeLPSArray：计算部分匹配表（LPS数组），用于存储模式字符串的部分匹配信息。这个函数的时间复杂度为O(m)，其中m是模式字符串的长度。

2. KMPSearch：使用KMP算法在主字符串中查找模式字符串的所有匹配位置。利用LPS数组减少匹配失败时的重复计算。这个函数的时间复杂度为O(n + m)，其中n是主字符串的长度，m是模式字符串的长度。

3. main：演示如何使用KMP算法在一个示例文本中搜索一个模式，并打印出匹配的位置。

你可以根据需要修改text和pattern字符串来测试不同的输入。这个实现清晰地展示了KMP算法的核心部分，包括计算LPS数组和实际的模式匹配过程。