Наименьшая повторяющаяся подстрока

Question

Я просматривал страницу с кодом Perl code (не спрашиваю почему) и наткнулся на это:

Отверстие 3 - наименьший повторяющийся узор

Напишите подпрограмму, которая принимает строку, которая может состоять из повторяющийся шаблон и возвращает наименьшую повторяющуюся подстроку. Если строка не состоит из повторяющегося шаблона, подпрограмма должен вернуть undef или пустую строку. 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, но я считаю, что оба значительно более читабельны.

Answer 2

Элегантность субъективна ...

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("")
}

Еще один, используя grouped:

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

Answer 3

Это эквивалентная однострочник Scala:

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