C++用KMP算法实现最长重复子串

好的，让我来解答你的问题。KMP算法是一种用来匹配字符串的算法，它的核心是计算出每个字符前缀的最长相同前缀和后缀的长度值，这个值可以帮助我们在匹配过程中避免重复比较已经匹配过的字符。在使用KMP算法实现最长重复子串时，我们可以通过不断缩小待查找字符串的长度，找到具有最长相同前缀和后缀的字符串。

代码实现如下：

#include <cstring>

int getNext(const char *s, int m, int *next) {
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < m; i++) {
        while (k >= 0 && s[k + 1] != s[i]) {
            k = next[k];
        }
        if (s[k + 1] == s[i]) {
            k++;
        }
        next[i] = k;
    } 
}

int longestRepeatSubstring(const char *s) {
    int n = strlen(s);
    int next[n];
    getNext(s, n, next);
    int ans = -1;
    for (int i = 0; i < n; i++) {
        int j = next[i];
        if (j >= 0 && i - j > ans) {
            ans = i - j;
        }
    }
    return ans;
}

在上述代码中，getNext函数用于计算最长相同前缀和后缀的长度值，使用了KMP算法的核心思想。在最后的longestRepeatSubstring函数中，我们通过遍历每个字符串前缀，找到具有最长相同前缀和后缀的字符串，并返回它的长度。

希望我的回答对你有所帮助！