最小重复子串

Question

我正在查看 Perl 代码高尔夫页面（不要问为什么）并发现了这个：

第 3 洞 - 最小重复图案

编写一个子例程，它接受一个字符串，该字符串可能包含 重复模式，并返回最小的重复子串。如果 该字符串不包含重复模式，子例程 应该返回 undef 或空字符串。例如：

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

优雅是主观的...

def smallestPat(input: String) = {
   (1 to input.length).view
      .map(i => input.take(i))
      .find{p => 
        Iterator.iterate(p)(_ + p)
          .takeWhile(_.length <= input.length)
          .exists(_ == input) && p != input}
      .getOrElse("")
}

List("aaaaaa", "ababab", "aabaab", "ababaa") map smallestPat
// res13: List[String] = List(a, ab, aab, "")

编辑和重新编辑：稍微短一些：

def smallestPat(i: String) = {
   (1 to i.length - 1)
      .map(i.take)
      .find(p => p * (i.length / p.length) == i)
      .getOrElse("")
}

再一个，使用分组：

def smallestPat(i: String) = {
  (1 to i.size/2).map(i.take)
  .find(p => i.grouped(p.size) forall(p==))
  .getOrElse("")
}

Answer 2

您愿意接受基于 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 那样简洁，但我发现两者都更具可读性。

Answer 3

这是等效的 Scala 单行代码：

"""(?:^(.*?)\1+$)|.*""".r replaceAllIn (_: String, "$1")