Return all indices of a specific substring

Question

Is there a Scala library API method (and if not, an idiomatic way) to get a list of all the indices for a substring (target) within a larger string (source)? I tried to browse through ScalaDoc but could not find anything obvious. There are so many methods that do so many useful things, I assume that I simply do not provide the correct search terms.

For example, if I have the source string "name: Yo, name: Jim, name: name, name: bozo" and I use the target string "name:", I would like to get List [Int] of the list back (0, 8, 17, 27).

Here is my quick hack to solve the problem:

def indexesOf(source: String, target: String, index: Int = 0, withinOverlaps: Boolean = false): List[Int] = { def recursive(index: Int, accumulator: List[Int]): List[Int] = { if (!(index < source.size)) accumulator else { val position = source.indexOf(target, index) if (position == -1) accumulator else { recursive(position + (if (withinOverlaps) 1 else target.size), position :: accumulator) } } } if (target.size <= source.size) { if (!source.equals(target)) { recursive(0, Nil).reverse } else List(0) } else Nil } 

Any guidance you can give me, replacing it with the appropriate standard library entry point, would be greatly appreciated.

UPDATE 2019 / JUN / 16:

Further code tightening:

  def indexesOf(source: String, target: String, index: Int = 0, withinOverlaps: Boolean = false): List[Int] = { def recursive(indexTarget: Int = index, accumulator: List[Int] = Nil): List[Int] = { val position = source.indexOf(target, indexTarget) if (position == -1) accumulator else recursive(position + (if (withinOverlaps) 1 else target.size), position :: accumulator) } recursive().reverse } 

UPDATE 2014 / July / 22:

Inspired by Siddhartha Datta's answer, I clarified my code. Now it looks like this:

  def indexesOf(source: String, target: String, index: Int = 0, withinOverlaps: Boolean = false): List[Int] = { @tailrec def recursive(indexTarget: Int, accumulator: List[Int]): List[Int] = { val position = source.indexOf(target, indexTarget) if (position == -1) accumulator else recursive(position + (if (withinOverlaps) 1 else target.size), position :: accumulator) } recursive(index, Nil).reverse } 

In addition, if I have the source string "aaaaaaaa" and I use the target string "aa", I would like to return List [Int] of List (0, 2, 4, 6) by default, which skips the search that starts inside the found substring . The default value can be overridden by passing "true" for the insideOverlaps parameter, which in the case of "aaaaaaaa" / "aa" returns List (0, 1, 2, 3, 4, 5, 6).

Answer 1

I always lean towards a bag of regular expression tricks with issues like this. I would not say that this is correct, but it is much less code. :)

 val r = "\\Qname\\E".r val ex = "name:Yo,name:Jim,name:name,name:bozo" val is = r.findAllMatchIn(ex).map(_.start).toList 

The quotes \\Q and \\E not needed for this case, but if the string you are looking for has some special characters, then it will.

Answer 2

A little code to get all the indices, call the method below as getAllIndexes (source, target)

 def getAllIndexes(source: String, target: String, index: Int = 0): List[Int] = { val targetIndex = source.indexOf(target, index) if(targetIndex != -1) List(targetIndex) ++ getAllIndexes(source, target, targetIndex+1) else List() }