Индексы подстроки в Smalltalk

Question

Кажется, реализации Smalltalk пропускают алгоритм, который возвращает все индексы подстроки в строке. Наиболее похожие возвращают только один индекс элемента, например: firstIndexesOf: in:, findSubstring :, findAnySubstring: варианты.

Существуют реализации в Ruby , но первая основана на взломе Ruby, вторая не работает, игнорируя перекрывающиеся строки, а последняя использует класс Enumerator, который я не знаю, как перевести в Smalltalk. Интересно, лучше ли начинать эту реализацию Python , поскольку она рассматривает оба случая, перекрывающиеся или нет, и не использует регулярные выражения.

Моя цель - найти пакет или метод, который обеспечивает следующее поведение:

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

Когда рассматривается перекрытие:

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

Когда перекрытие не учитывается:

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

В Pharo, когда текст выбран на игровой площадке, сканер обнаруживает подстроку и выделяет совпадения. Однако я не смог найти строковую реализацию этого.

Мои лучшие усилия на данный момент приводят к реализации в 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 предлагает разные подходы.

Леандро опередил меня в коде (и его код более эффективен), но я уже написал его, поэтому я тоже поделюсь им. Прислушайтесь к его совету о том, что 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

Я исправил некоторые проблемы, которые произошли со мной. Не забудьте проверить это как можно больше!

Answer 2

Позвольте мне сначала уточнить, что коллекции 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

Убедитесь, что вы написали несколько юнит-тестов (и не забывайте выполнять граничные случаи!)