十一届蓝桥杯 c 重复字符串

题目描述：

给定一个字符串s，求出该字符串的最长重复子串长度。

输入格式：

第一行为一个整数n，表示字符串的长度。

第二行为一个字符串s。

输出格式：

输出一个整数，表示该字符串的最长重复子串长度。

样例输入：

6
ababab

样例输出：

3

算法1：

(后缀数组) $O(nlog^2n)$

我们可以将字符串的所有后缀排序，然后求相邻两个后缀的最长公共前缀，最后取所有公共前缀中的最大值即可。

具体来说，我们可以使用后缀数组来对字符串的所有后缀进行排序，然后使用倍增算法求出相邻两个后缀的最长公共前缀。

时间复杂度：

- 后缀数组的构建时间复杂度为O(nlogn)。
- 最长公共前缀的计算时间复杂度为O(nlogn)。

因此，总时间复杂度为O(nlog^2n)。

C++ 代码

算法2：

(哈希) $O(nlogn)$

我们可以将字符串s拆分成多个子串，然后对每个子串进行哈希，最后使用二分查找的方式找到最长的重复子串。

具体来说，我们可以将字符串s拆分成多个子串，然后对每个子串进行哈希。哈希算法可以使用Rabin-Karp算法，时间复杂度为O(n)。

找到哈希值相同的两个子串后，我们可以使用二分查找来判断这两个子串的最长公共前缀的长度。二分查找的时间复杂度为O(logn)。

时间复杂度：

- 哈希的时间复杂度为O(n)。
- 二分查找的时间复杂度为O(logn)。

因此，总时间复杂度为O(nlogn)。

C++ 代码

算法3：

(Manacher算法) $O(n)$

Manacher算法是一种可以在线性时间内找到一个字符串的所有回文子串的算法。

该算法的核心思想是利用回文子串的对称性，来避免重复计算。具体来说，我们可以通过维护最右边的回文子串的右端点来避免重复计算。

时间复杂度：

该算法的时间复杂度为O(n)。

C++ 代码