User:

用C++实现KMP算法，并加上中文注释

Assistant:

KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，用于查找一个字符串在另一个字符串中的所有出现位置。以下是KMP算法的C++实现，包括中文注释：

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

// 前缀函数的计算
std::vector<int> computeLPS(const std::string& pattern) {
    int M = pattern.length();
    std::vector<int> lps(M, 0); // lps数组，存储前缀的最长匹配长度

    int len = 0; // lps数组的当前长度
    lps[0] = 0; // lps[0]总是0

    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算法实现
int KMPSearch(const std::string& text, const std::string& pattern) {
    int M = pattern.length();
    int N = text.length();

    std::vector<int> lps = computeLPS(pattern);

    int i = 0; // text的当前位置
    int j = 0; // pattern的当前位置

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

        if (j == M) {
            // 如果匹配完成，返回匹配的起始位置
            return i - M;
        } else if (i < N && pattern[j]!= text[i]) {
            // 如果不匹配，且text的当前字符不在pattern的前缀中
            if (j!= 0) {
                // 使用lps数组中的值来移动j
                j = lps[j - 1];
            } else {
                // 如果j为0，直接移动i
                i++;
            }
        }
    }

    // 如果text中没有匹配到的pattern，返回-1
    return -1;
}

int main() {
    std::string text = "ABC ABCDAB ABCDABCDABDE";
    std::string pattern = "ABCDABD";

    int result = KMPSearch(text, pattern);
    if (result!= -1) {
        std::cout << "Pattern found at index " << result << std::endl;
    } else {
        std::cout << "Pattern not found" << std::endl;
    }

    return 0;
}

这段代码首先定义了一个计算前缀函数（lps数组）的函数computeLPS，然后定义了KMP算法的主函数KMPSearch。KMPSearch函数接收两个参数text和pattern，分别表示要搜索的文本和模式字符串。函数返回模式字符串在文本中的第一个匹配位置的索引，如果没有匹配则返回-1。

在main函数中，我们提供了一个例子，搜索文本"ABC ABCDAB ABCDABCDABDE"中的模式"ABCDABD"。如果找到匹配，输出将是"Pattern found at index"，随后是匹配的起始索引。如果没有找到匹配，输出将是"Pattern not found"。

请注意，这段代码假设输入文本和模式字符串只包含小写英文字母和中文字符。如果需要处理其他字符集，可能需要适当调整。

Citation

If our Llama3-8B-Chinese-Chat is helpful, please kindly cite as:

@misc {shenzhi_wang_2024,
    author       = {Wang, Shenzhi and Zheng, Yaowei},
    title        = { Llama3-8B-Chinese-Chat (Revision 6622a23) },
    year         = 2024,
    url          = { https://huggingface.co/shenzhi-wang/Llama3-8B-Chinese-Chat },
    doi          = { 10.57967/hf/2316 },
    publisher    = { Hugging Face }
}