5

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

Ruby 中有一些实现，但第一个依赖于 Ruby hack，第二个无法忽略重叠字符串，最后一个使用 Enumerator 类，我不知道如何将其转换为 Smalltalk。我想知道这个Python 实现是否是开始的最佳途径，因为考虑了两种情况，重叠与否，并且不使用正则表达式。

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

'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
4

2 回答 2

5

首先让我澄清一下 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

确保您编写了一些单元测试（并且不要忘记练习边界情况！）

于 2018-07-05T12:48:00.150 回答
1

已编辑

如果你能告诉我们你需要在“更大的画面”中实现什么，那也很好。有时 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

我已经解决了一些发生在我身上的问题。不要忘记尽可能多地测试它！

于 2018-07-05T15:23:07.437 回答