返回特定子字符串的所有索引

Question

有没有Scala库API方法（如果没有，有没有惯用的方法）可以获取较大字符串（源）中子字符串（目标）的所有索引列表？我尝试查看了ScalaDoc，但没有找到任何明显的东西。有很多方法做很多有用的事情，我猜我只是没有提交正确的搜索词。

例如，如果我有一个源字符串“name:Yo,name:Jim,name:name,name:bozo”，并使用一个目标字符串“name:”，那么我想得到一个List[Int]，其中包含List(0, 8, 17, 27)。

这是我的快速解决问题的方法：

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
  }

如果您能指导我用适当的标准库入口替换它，将不胜感激。

更新于2019年6月16日：

进一步压缩代码：

  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
  }

更新时间：2014年7月22日：

受Siddhartha Dutta答案的启发，我进一步优化了我的代码。现在它看起来像这样：

  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
  }

此外，如果我有一个源字符串 "aaaaaaaa"，并使用目标字符串 "aa"，我希望默认情况下返回一个List[Int]，其中包含跳过在已找到的子字符串内开始搜索的位置 List(0, 2, 4, 6)。可以通过将 withinOverlaps 参数设置为 "true" 来覆盖默认情况，在 "aaaaaaaa"/"aa" 的情况下，它会返回 List(0, 1, 2, 3, 4, 5, 6)。

- chaotic3quilibrium

---

没有“标准方法”。另外，由于这是工作代码，因此最好适合进行代码审查。 - user2864740

@chaotic3quilibrium，你能否将这个方法使用BSD许可证，这样如果我复制或改编它，老板就不会生气了吗？ :) - ericpeters

据我所知，StackOverflow 上发布的任何代码片段都可以被视为公共领域；也就是说，没有任何许可证限制您剪切/粘贴/修改/自定义片段以适应您需要的任何上下文。@ericpeters - chaotic3quilibrium

@chaotic3quilibrium 这是一个有趣的灰色地带，直到三月份（http://meta.stackexchange.com/questions/271080/the-mit-license-clarity-on-using-code-on-stack-overflow-and-stack-exchange）他们才会在归属方面变得类似于MIT。 - ericpeters

你应该更新答案，使用Vector（并追加而不是预先添加）而不是List，以避免在最后进行额外的.reverse操作。可能还有助于返回类型IndexedSeq[Int]。 - ericpeters

Answer 1

在像这样的问题上，我总是倾向于使用正则表达式技巧。虽然它并不是“恰当”的解决方案，但代码量要少得多。 :)

val r = "\\Qname\\E".r
val ex = "name:Yo,name:Jim,name:name,name:bozo"

val is = r.findAllMatchIn(ex).map(_.start).toList

< p >引号\\Q和\\E在这种情况下并不是必需的，但如果您要查找的字符串包含任何特殊字符，则需要使用它们。

- joescii

---

非常好。在我编写Scala代码之前，我只花了不到两分钟来评估正则表达式方法。拥有多种查找字符串的方法真是太好了。 - chaotic3quilibrium

顺便说一下，如果你想使用纯正则表达式（作为从其他来源未转义的复制/粘贴），你也可以将第一行更改为"""\Qname\E""".r。Scala中的三重引号选项真是太棒了！ - chaotic3quilibrium

Answer 2

获取所有索引的小代码
调用下面的方法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()
      }

- Siddhartha Dutta

---

这似乎返回了反向列表，即List(27, 17, 8, 0)，对吗？此外，您可以优化两个if路径。第一个用"targetIndex :: get..."替换"List(targetIndex) ++ get..."。第二个用"Nil"替换"List()"。 - chaotic3quilibrium

该方法按照索引升序返回列表，即List(0,8,17,27)。优化是正确的。 - Siddhartha Dutta

我刚刚尝试了你的调用，在添加了@tailrec注释后，我得到了一个编译器错误，指出它不是尾递归（无论是++还是::）。然而，你更简洁的代码给了我灵感，所以我提供了一个更新来展示我的代码变得更紧凑。我还添加了另一个测试用例（"aaaaaaaa"，"aa"示例），以展示可选的withinOverlaps参数的好处。 - chaotic3quilibrium

是的，这个方法不是尾递归的，因为它首先调用自身，然后再添加结果。 - Siddhartha Dutta

啊。我有一个字符串，我会得到数百到数千个回复，而且不能承受可能会炸掉调用堆栈的情况。 - chaotic3quilibrium