kmp字符串相同子串的个数c++

KMP（Knuth-Pratt）算法是一种用于查找字符串中特定子串出现次数的经典技术，特别是在处理大量数据时，其效率相对较高。在C++中，我们可以使用该算法来计算两个字符串之间的匹配位置，进而推断出相同子串的数量。

KMP算法的核心在于构建一个失配指针数组，这个数组可以帮助我们在搜索过程中跳过不必要的比较，提高匹配速度。以下是步骤概览：

1. **创建部分匹配表（Partial Match Table, PMT）**：根据模式字符串计算失配指针。PMT[i]表示如果模式的第一个i+1位与主串匹配失败，则应该跳转到模式的多少位置继续尝试。

2. **匹配过程**：对于主串中的每个字符，与模式进行逐个比较。如果匹配，继续移动；如果不匹配，查看PMT找到适当的跳转位置。

3. **计数相同子串**：每当遇到完整的匹配（包括原模式和非空的前缀），就增加计数器，并继续从下一个位置开始新一轮的匹配。

C++实现KMP算法并计算相同子串数量的一个基本版本可能会这样设计：

#include <vector>
#include <string>

std::vector<int> getPMTable(const std::string &pattern) {
    int n = pattern.size();
    std::vector<int> pm(n);
    for (int i = 1, j = -1; i < n; ++i) {
        while (j != -1 && pattern[i] != pattern[j + 1]) {
            j = pm[j];
        }
        if (pattern[i] == pattern[j + 1]) {
            ++j;
        }
        pm[i] = j;
    }
    return pm;
}

int countSubstrings(std::string text, const std::string &pattern) {
    int m = pattern.length();
    std::vector<int> pm = getPMTable(pattern);
    int count = 0;
    int i = 0, j = 0;

    while (i < text.length()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else if (j != 0) {
            j = pm[j - 1];
        } else {
            i++;
        }

        if (j == m) { // 完整匹配
            count++;
            j = pm[j - 1]; // 跳回下一个位置
        }
    }

    return count;
}