Индексы подстроки в 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.

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

string smalltalk pharo visualworks dolphin-smalltalk
person user1000565    schedule 04.07.2018    source источник
comment
Могу ли я призвать вас (попытаться) реализовать этот метод самостоятельно? Правила SO устанавливают, что вопросы должны требовать некоторого усилия по кодированию; покажи нам свою.   -  person Leandro Caniglia    schedule 05.07.2018
comment
Результаты вашего примера overlappling: true и overlapping: false кажутся обратными?   -  person lurker    schedule 05.07.2018
comment
пожалуйста, не забудьте отметить ваши вопросы отвеченными, когда вы довольны ответом! Подробнее см. stackoverflow.com/help/someone-answers.   -  person tukan    schedule 09.07.2018

Ответы (2)


arrow_upward
5
arrow_downward

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

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

person Leandro Caniglia    schedule 05.07.2018
comment
Спасибо за ваши заметки. Не эффективнее ли в Smalltalk делать [ (var := exp) > 0 ] ..., чем [ var := exp. var > 0 ] - person user1000565; 06.07.2018
comment
@ user1000565 Пожалуйста, откройте еще один вопрос по этой интересной проблеме. - person Leandro Caniglia; 06.07.2018
comment
мне только что пришло в голову, что назначение i := aBoolean ... лишнее. Разве это не так? Просто aBoolean ifTrue: [i := i + 1] ifFalse: [i := i + n] должно быть достаточно. - person tukan; 13.07.2018
comment
@tunkan, ты прав. Обычно я выношу задание за пределы блоков. Я меняю код... Спасибо! - person Leandro Caniglia; 13.07.2018

arrow_upward
1
arrow_downward

Отредактировано

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

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

person tukan    schedule 05.07.2018
comment
Я думаю, что currentPosition не может быть nil, потому что findString:startingAt: отвечает 0, когда подстрока не найдена. В любом случае, было хорошей идеей предоставить свою версию метода. - person Leandro Caniglia; 06.07.2018
comment
@LeandroCaniglia спасибо за исправление опечатки :) в startAt:. Это отстой, когда копипаста не работает правильно с SO. Вы, конечно, правы насчет 0, когда ничего не найдено. Я скорректировал код. (У меня был код в рабочей области, и мне пришлось преобразовать его в селектор). - person tukan; 06.07.2018