string - Smalltalk 中子串的索引

Question

似乎 Smalltalk 实现错过了一种算法，该算法返回字符串中子字符串的所有索引。最相似的只返回元素的一个索引，例如: firstIndexesOf:in: 、 findSubstring: 、 findAnySubstring: 变体。

有implementations in Ruby但是第一个依赖于 Ruby hack，第二个在忽略重叠字符串时不起作用，最后一个使用 Enumerator 类，我不知道如何将其转换为 Smalltalk。我想知道这个 Python implementation是最好的起点，因为考虑了两种情况，重叠与否，并且不使用正则表达式。

我的目标是找到一个提供以下行为的包或方法:

'ABDCDEFBDAC' indicesOf: 'BD'. "#(2 8)"

当考虑重叠时:

'nnnn' indicesOf: 'nn' overlapping: true. "#(0 2)"

不考虑重叠时:

'nnnn' indicesOf 'nn' overlapping: false. "#(0 1 2)"

在 Pharo 中，当在 Playground 中选择文本时，扫描仪会检测子字符串并突出显示匹配项。但是我找不到这个的 String 实现。

到目前为止，我的最大努力在 String (Pharo 6) 中实现了这个实现:

indicesOfSubstring: subString
  | indices i |

  indices := OrderedCollection new: self size.
  i := 0.
  [ (i := self findString: subString startingAt: i + 1) > 0 ] whileTrue: [
    indices addLast: i ].
  ^ indices

Answer 1

首先让我澄清一下，Smalltalk 集合是基于 1 的，而不是基于 0 的。因此你的例子应该阅读

'nnnn' indexesOf: 'nn' overlapping: false. "#(1 3)"
'nnnn' indexesOf: 'nn' overlapping: true. "#(1 2 3)"

请注意，我也注意到了 @lurker 的观察(并且也调整了选择器)。

现在，从您的代码开始，我将对其进行如下更改:

indexesOfSubstring: subString overlapping: aBoolean
  | n indexes i |
  n := subString size.
  indexes := OrderedCollection new.                            "removed the size"
  i := 1.                                                      "1-based"
  [
    i := self findString: subString startingAt: i.             "split condition"
    i > 0]
  whileTrue: [
    indexes add: i.                                            "add: = addLast:"
    i := aBoolean ifTrue: [i + 1] ifFalse: [i + n]].           "new!"
  ^indexes

确保您编写了一些单元测试(并且不要忘记练习边界案例!)