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

Кажется, реализации 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
Источник

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

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

Источник

отредактированный

Также было бы неплохо, если бы вы рассказали нам, чего вам нужно достичь в "большей картине". Иногда 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

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

Источник
Другие вопросы по тегам