在所给字符串中找出最少出现两次的最长子串的长度,没有则输出0。 输入格式:这一定是非空的字符串S,并由小写字母组成。 输出格式:输出一个数。这个数是子串中最少出现两次的最长子串的长度。 用java写出这道算法题
时间: 2023-04-03 21:05:09 浏览: 60
我可以回答这个问题。这道算法题可以使用后缀数组和最长公共前缀数组来解决。首先,我们需要构建后缀数组,然后计算最长公共前缀数组。接下来,我们可以遍历最长公共前缀数组,找到最长的公共前缀长度,这个长度就是最少出现两次的最长子串的长度。如果最长公共前缀长度为0,则输出0。以下是Java代码实现:
public static int findLongestSubstring(String s) {
int n = s.length();
int[] sa = new int[n];
int[] rank = new int[n];
int[] height = new int[n];
int[] cnt = new int[Math.max(n, 256)];
int[] tmp = new int[n];
for (int i = 0; i < n; i++) {
cnt[s.charAt(i)]++;
}
for (int i = 1; i < cnt.length; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
sa[--cnt[s.charAt(i)]] = i;
}
rank[sa[0]] = 0;
int k = 1;
while (k < n) {
int p = 0;
for (int i = n - k; i < n; i++) {
tmp[p++] = i;
}
for (int i = 0; i < n; i++) {
if (sa[i] >= k) {
tmp[p++] = sa[i] - k;
}
}
Arrays.fill(cnt, 0);
for (int i = 0; i < n; i++) {
cnt[rank[tmp[i]]]++;
}
for (int i = 1; i < cnt.length; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
sa[--cnt[rank[tmp[i]]]] = tmp[i];
}
int[] newRank = new int[n];
newRank[sa[0]] = 0;
p = 1;
for (int i = 1; i < n; i++) {
int x = sa[i - 1];
int y = sa[i];
if (rank[x] == rank[y] && rank[x + k] == rank[y + k]) {
newRank[y] = p - 1;
} else {
newRank[y] = p++;
}
}
rank = newRank;
if (p >= n) {
break;
}
k *= 2;
}
k = 0;
for (int i = 0; i < n; i++) {
if (rank[i] == 0) {
height[rank[i]] = 0;
continue;
}
if (k > 0) {
k--;
}
int j = sa[rank[i] - 1];
while (i + k < n && j + k < n && s.charAt(i + k) == s.charAt(j + k)) {
k++;
}
height[rank[i]] = k;
}
int maxLen = 0;
for (int i = 1; i < n; i++) {
if (height[i] > maxLen) {
maxLen = height[i];
}
}
return maxLen > 0 ? maxLen : 0;
}