Найти самую длинную повторяющуюся подстроку в строке?
Я наткнулся на программу ниже, которая выглядит идеально. По моему мнению, его временная сложность равна nlogn, где n - длина строки.
n для хранения разных строк, nlog для сортировки, n для сравнения. Таким образом, сложность времени не имеет значения. Пространство сложность n для хранения n подстрок
Мой вопрос, может ли это быть дополнительно оптимизировано?
public class LRS {
// return the longest common prefix of s and t
public static String lcp(String s, String t) {
int n = Math.min(s.length(), t.length());
for (int i = 0; i < n; i++) {
if (s.charAt(i) != t.charAt(i))
return s.substring(0, i);
}
return s.substring(0, n);
}
// return the longest repeated string in s
public static String lrs(String s) {
// form the N suffixes
int n = s.length();
String[] suffixes = new String[n];
for (int i = 0; i < n; i++) {
suffixes[i] = s.substring(i, n);
}
// sort them
Arrays.sort(suffixes);
// find longest repeated substring by comparing adjacent sorted suffixes
String lrs = "";
for (int i = 0; i < n-1; i++) {
String x = lcp(suffixes[i], suffixes[i+1]);
if (x.length() > lrs.length())
lrs = x;
}
return lrs;
}
public static void main(String[] args) {
String s = "MOMOGTGT";
s = s.replaceAll("\\s+", " ");
System.out.println("'" + lrs(s) + "'");
}
}