Smallest repeating substring

Question

I looked at the Perl golf code page (don't ask why) and came across this:

Hole 3 - smallest repeating pattern

Write a subroutine that takes 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 routine should return undef or an empty string. eg:.

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

Apparently, in Perl this can be expressed as sub g3 { pop=~/^(.*?)\1+\z/s&&$1 }

I don’t know much Perl, so I don’t understand how it works. What is the best we can do in Scala? I'm more interested in elegance than the exact number of characters.

Here is my attempt, but it is pretty ugly, that’s why I ask.

 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

Elegance is subjective ...

 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, "") 

Edit and edit: a little shorter:

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

Another one using grouped :

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

Answer 2

Are you ready to make a decision based on Regex ?

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

Or single line:

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

Not as concise as Perl, but I think they are significantly readable.

Answer 3

This is the Scala single line equivalent:

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