CODEWITHSUNDEEP
scalafunctional-programming
ferk86
ferk86

Reputation: 2345

Find all indices of pattern in string?

Here is the code I have which looks ugly because it uses two vars.

  def patternMatching(pattern: String, genome: String): List[Int] = {
    assert(pattern.length < genome.length)
    var curr = 0
    var r = List[Int]()
    while (curr != -1) {
      curr = genome.indexOf(pattern, curr)
      if (curr != -1) {
        r ::= curr
        curr += 1
      }
    }
    r.reverse
  }

How do you write this in a functional way?

Upvotes: 1

Views: 3315

Answers (4)

Danilo Burbano
Danilo Burbano

Reputation: 1

If you require to know also the ending position of the index you could use:

def patternMatchingIndex(pattern: Regex, text: String): List[(Int, Int)] =
  pattern.findAllMatchIn(text).map(index => (index.start, index.end)).toList

Upvotes: 0

Anton Ivanov
Anton Ivanov

Reputation: 51

There is a much simpler idiomatic Scala solution that does not require trying to explicitly apply a pattern at every location or using 3rd party library:

def patternMatching(pattern: String, genome: String): List[Int] =
  pattern.r.findAllMatchIn(genome).map(_.start).toList

Upvotes: 1

Yann Moisan
Yann Moisan

Reputation: 8281

It's quite straigthforward : 

0.until(genome.length).filter(genome.startsWith(pattern, _))

Upvotes: 10

senia
senia

Reputation: 38045

You could use unfold method from scalaz like this:

import scalaz._, Scalaz._

def patternIndexes(pattern: String, genome: String) = unfold(0){
  genome.indexOf(pattern, _) match {
    case -1 => None
    case n => (n, n+1).some
  }
}

Usage:

scala> patternIndexes("a", "aba").toList
res0: List[Int] = List(0, 2)

Upvotes: 2

Related Questions