能否把时间复杂度优先到 o(nlog n)以内
时间: 2023-11-29 22:05:27 浏览: 88
是的,我们可以使用一些高效的算法来将时间复杂度优化到 O(n log n) 以内。
一种常见的方法是使用后缀数组和最长公共前缀 (LCP) 数组。后缀数组是一个数组,其中包含将一个字符串的所有后缀按字典序排列后的索引。LCP 数组是一个数组,其中包含相邻后缀的最长公共前缀的长度。
我们可以首先使用后缀数组对字符串进行排序,然后使用 LCP 数组来计算重复次数。具体来说,我们可以遍历 LCP 数组,并在每个位置上查找前一个后缀和当前后缀的 LCP。如果 LCP 的长度大于当前重复的次数,则将重复次数更新为 LCP 的长度。最后返回重复次数即可。
以下是一个 Java 代码实现:
```
public static int countRepeats(String s) {
int n = s.length();
int[] sa = suffixArray(s);
int[] lcp = lcpArray(s, sa);
int repeats = 0;
for (int i = 1; i < n; i++) {
int len = lcp[i];
if (len > repeats) {
repeats = len;
}
}
return repeats;
}
private static int[] suffixArray(String s) {
int n = s.length();
Integer[] sa = new Integer[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
sa[i] = i;
rank[i] = s.charAt(i);
}
for (int k = 1; k < n; k *= 2) {
Arrays.sort(sa, Comparator.comparing(i -> rank[i]));
int[] tmp = new int[n];
int r = 0;
for (int i = 0; i < n; i++) {
if (i > 0 && rank[sa[i-1]] == rank[sa[i]] && sa[i-1]+k < n && rank[sa[i-1]+k/2] == rank[sa[i]+k/2]) {
tmp[sa[i]] = r;
} else {
tmp[sa[i]] = ++r;
}
}
rank = tmp;
}
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[sa[i]] = i;
}
return res;
}
private static int[] lcpArray(String s, int[] sa) {
int n = s.length();
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
rank[sa[i]] = i;
}
int[] lcp = new int[n];
int h = 0;
for (int i = 0; i < n; i++) {
if (rank[i] > 0) {
int j = sa[rank[i]-1];
while (i+h < n && j+h < n && s.charAt(i+h) == s.charAt(j+h)) {
h++;
}
lcp[rank[i]] = h;
if (h > 0) {
h--;
}
}
}
return lcp;
}
```
该方法首先使用 `suffixArray` 方法计算字符串 s 的后缀数组。然后使用 `lcpArray` 方法计算 s 的 LCP 数组。最后遍历 LCP 数组,计算重复次数。其中 `suffixArray` 和 `lcpArray` 方法都是经典的算法,可以在各种算法书籍或网站上找到详细的说明。
相关推荐
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)