对串S1="abaabaabcaba"和串S2= "abaabc"进行KMP匹配算法的代码C＋＋

KMP（Knuth-Pratt）算法是一种高效的字符串匹配算法，用于在一个文本串（主串）中查找模式串是否存在。下面是使用 C++ 实现 KMP 算法匹配 S1 和 S2 的简单代码：

首先，你需要计算 KMP 滚动数组（next数组），用于存储模式串中每个位置的最大前缀和后缀公共长度。对于给定的模式串 S2:

const char* pattern = "abaabc";
size_t patternLength = strlen(pattern);
int next[patternLength] = {0}; // 初始化所有元素为0

for (size_t i = 1, j = -1; i < patternLength; ++i) {
    while (j != -1 && pattern[i] != pattern[j + 1]) {
        j = next[j];
    }
    if (pattern[i] == pattern[j + 1]) {
        j++;
    }
    next[i] = j;
}

然后，在主函数 main 中进行 KMP 匹配：

SString text1("abaabaabcaba");
SString text2("abaabc");

bool isMatch = true;
size_t index = 0;

for (size_t i = 0; i < text1.length; ++i) {
    if (index == text2.length) { // 如果找到整个模式串，匹配成功
        cout << "Pattern found at position " << i - text2.length + 1 << endl;
        break;
    }

    if (text1.ch[i] == text2.ch[index]) {
        index++;
    } else {
        if (index != 0) { // 如果当前字符不匹配，尝试使用 next 数组
            index = next[index - 1];
        } else {
            isMatch = false;
            break; // 如果第一个字符就不匹配，直接结束
        }
    }
}

if (isMatch) {
    cout << "S1与S2匹配" << endl;
} else {
    cout << "S1与S2不匹配" << endl;
}

这段代码首先生成了 KMP 滚动数组 `next`，然后遍历主串 `text1`，每次与模式串 `text2` 相比，如果不匹配则借助 `next` 数组回溯。

相关问题：
1. KMP 算法的时间复杂度是多少？
2. 当文本串和模式串都很大时，如何优化这个过程？
3. 如何解释 KMP 算法中的“滑动窗口”原理？