Smalltalk 中子串的索引

Question

似乎 Smalltalk 实现错过了一个算法，该算法 return 字符串中子字符串的所有索引。最相似的 returns 只有一个元素的一个索引，例如：firstIndexesOf:in:, findSubstring:, findAnySubstring: variants。

but the first one relies on a Ruby hack, the second one does not work ignoring overlapping Strings and the last one uses an Enumerator class which I don't know how to translate to Smalltalk. I wonder if this 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 (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

确保你写了一些单元测试（并且不要忘记练习边界案例！）

Answer 2

已编辑

如果您能告诉我们您需要在 "greater picture" 中实现什么，那也很好。有时 Smalltalk 会提供不同的方法。

Leandro 比我先写了代码（他的代码效率更高），但我已经写好了，所以我也来分享一下。听取他关于 Smalltalk 基于 1 => 重写示例的建议。

示例中我使用了 Smalltalk/X 和 Pharo 6.1。

代码为：

indexesOfSubstring: substringToFind overlapping: aBoolean

    | substringPositions aPosition currentPosition |

    substringPositions := OrderedSet new. "with overlap on you could get multiple same 
              positions in the result when there is more to find in the source string"

    substringToFindSize := substringToFind size. "speed up for large strings"
    aPosition := 1.

    [ self size > aPosition ] whileTrue: [
        currentPosition := self findString: substringToFind startingAt: aPosition.
        (currentPosition = 0) ifTrue: [ aPosition := self size + 1 ] "ends the loop substringToFind is not found"
                             ifFalse: [
                                 substringPositions add: currentPosition.
                                 aBoolean ifTrue: [ aPosition := aPosition + 1 ] "overlapping is on"
                                         ifFalse: [ aPosition := currentPosition + substringToFindSize ] "overlapping is off"
                             ]
    ].

    ^ substringPositions

我已经解决了我遇到的一些问题。不要忘记尽可能多地测试它！

Smalltalk 中子串的索引

Indices of a substring in Smalltalk

string

smalltalk

visualworks

pharo

dolphin-smalltalk