实验目的：

本实验旨在分析和测试KMP算法的实现，并研究其在字符串搜索中的应用。

实验内容：

a 问题分析：

• 如何构建最长前缀后缀匹配表（LPS数组）以提高搜索效率？
• 如何在文本字符串中执行匹配，利用LPS数组来避免不必要的字符比较？
• 如何设计算法以实现模式字符串的搜索？

b 算法设计：

KMP算法的设计包括以下关键步骤：

• 构建LPS数组：使用computeLPSArray函数来计算模式字符串的LPS数组，该数组指示了模式字符串中每个位置的前缀和后缀的最长匹配长度。
• 在文本中执行匹配：使用KMPSearch函数，该函数在文本字符串中执行模式字符串的匹配。它使用LPS数组来智能地回溯，以提高搜索效率。

c 数据结构设计：

在这次实验中，我使用了以下数据结构：

• 字符串：用于表示文本字符串和模式字符串。
• 向量（vector）：用于存储LPS数组。
• 整数变量：用于表示匹配过程中的索引。

d 调试过程：

在编写和测试代码时，我遇到了一些可能的问题，如逻辑错误或边界情况。这些问题需要仔细调试，以确保算法的正确性和性能。通过逐步调试和打印输出结果，我确认代码能够正确地找到模式字符串在文本中的匹配位置。

e 输出结果：

以下是一些示例输出结果：

• 当文本字符串为"ABABDABACDABABCABAB"，模式字符串为"ABABCABAB"时，KMP算法找到了模式字符串在文本中的匹配位置：

  在索引 10 处找到匹配串

• 当文本字符串和模式字符串由用户输入时，KMP算法会在用户提供的文本中查找用户提供的模式，并输出匹配位置。

f 源代码：

#include<bits/stdc++.h>
using namespace std;

// 计算匹配字符串的最长前缀后缀匹配表（LPS数组）
void computeLPSArray(const string& pattern, vector<int>& lps) {
    int length = 0;  // 前一个最长前缀后缀匹配的长度

    lps[0] = 0;  // lps[0] 总是为 0

    int i = 1;

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

// 使用KMP算法在文本中搜索匹配字符串
void KMPSearch(const string& text, const string& pattern) {
    int m = pattern.length();
    int n = text.length();

    vector<int> lps(m);
    computeLPSArray(pattern, lps);

    int i = 0;  // 用于文本[]
    int j = 0;  // 用于匹配串[]

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

        if (j == m) {
            // 找到匹配串，打印起始位置
            cout << "在索引 " << i - j << " 处找到匹配串" << endl;
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

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

//     KMPSearch(text, pattern);

//     return 0;
// }


int main() {
    string text;
    string pattern;
    cin>>text;
    cin>>pattern;

    KMPSearch(text, pattern);

    return 0;
}