scala - 最小重复子串

Question

我在看一个 Perl code golf page (不要问为什么)并遇到了这个:

Hole 3 - Smallest Repeating Pattern

Write a subroutine that accepts a string which may consist of a repeating pattern, and returns the smallest repeating substring. If the string does not consist of a repeating pattern, the subroutine should return undef or the empty string. e.g.:

input    output 
'aaaaaa' 'a' 
'ababab' 'ab' 
'aabaab' 'aab' 
'ababaa' ''

显然在 Perl 中，这可以表示为 sub g3 { pop=~/^(.*?)\1+\z/s&&$1 }
我对 Perl 了解不多，所以我不明白这是如何工作的。我们在 Scala 中能做的最好的事情是什么？我对优雅比精确的字符数更感兴趣。

这是我的尝试，但它非常丑陋，这就是我问的原因。

def srp(s: String) =
  s.inits.toList.tail.init.map(i => (i * (s.size / i.size), i)).
    filter(_._1 == s).map(_._2).reverse.headOption.getOrElse("")

Answer 1

你愿意承认Regex基于解决方案？

def srp(s: String) = {
  val M = """^(.*?)\1+$""".r
  s match {
    case M(m) => Some(m)
    case _ => None
  }
}

或单线:

val srp = """^(.*?)\1+$""".r.findFirstMatchIn(_: String).map(_.group(1))

不像 Perl 那样简洁，但我发现两者都更具可读性。