Поиск самой длинной повторяющейся подстроки. Осторожно: Scala.

[conjuncte]

Помогаю коллеге осваиваться в программировании. Предложил решить задачку: написать программу, которая в заданной строке найдет самую длинную повторяющуюся подстроку. Дополнительное ограничение: подстроки не должны пересекаться. Например, в строке "ABABA" это будет "AB", но не "ABA". В русской википедии такая задача почему-то не встречается, даю ссылку на английскую: Longest repeated substring.

Мое решение на Scala, не очень эффективное, в худшем случае О(n2), но его можно придумать за 15 минут и во время собеседования:

def longestRepeatedSubstring(str: String): Option[String] =
(1 to str.length / 2).reverse
.map(x => str.sliding(x))
.map(x => (for (s <- x) yield s)
.filter(s => str.indexOfSlice(s) + s.length <= str.lastIndexOfSlice(s)))
.filterNot(_.isEmpty)
.headOption
.map(_.next)

longestRepeatedSubstring("A")              // None
longestRepeatedSubstring("AA")             // Some(A)
longestRepeatedSubstring("AAA")            // Some(A)
longestRepeatedSubstring("ABC")            // None
longestRepeatedSubstring("AAAA")           // Some(AA)
longestRepeatedSubstring("ABCDABCDABC")    // Some(ABCD)
longestRepeatedSubstring("UUABCDABCDABC")  // Some(ABCD)

Предложите более элегантные решения?