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

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

Есть реализации в 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

Могу я посоветовать (попробовать) реализовать этот метод самостоятельно? Правила SO устанавливают, что вопросы должны показывать некоторые усилия по кодированию; покажи нам свой.

Leandro Caniglia 04.07.2018 23:48

Результаты вашего примера overlappling: true и overlapping: false кажутся обратными?

lurker 05.07.2018 04:33

пожалуйста, не забудьте отметить свои вопросы отвеченными, когда вы будете довольны ответом! Подробнее см. stackoverflow.com/help/someone-answers

tukan 09.07.2018 11:01
В чем разница между методом "==" и equals()
В чем разница между методом "==" и equals()
Это один из наиболее часто задаваемых вопросов новичкам на собеседовании. Давайте обсудим его на примере.
Замена символа по определенному индексу в JavaScript
Замена символа по определенному индексу в JavaScript
В JavaScript существует несколько способов заменить символ в строке по определенному индексу.
5
3
729
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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 для выполнения [ (var := exp) > 0 ] ..., чем [ var := exp. var > 0 ]

user1000565 06.07.2018 06:24

@ user1000565 Пожалуйста, откройте еще один вопрос по этому интересному выпуску.

Leandro Caniglia 06.07.2018 07:29

мне просто пришло в голову, что назначение i := aBoolean ... лишнее. Не правда ли? Просто aBoolean ifTrue: [i := i + 1] ifFalse: [i := i + n] должно хватить.

tukan 13.07.2018 16:07

@tunkan, ты прав. Обычно я перемещаю задание за пределы блоков. Меняю код ... Спасибо!

Leandro Caniglia 13.07.2018 16:42

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

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

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

Я думаю, что currentPosition не может быть nil, потому что findString:startingAt: отвечает 0, когда подстрока не найдена. В любом случае, было хорошей идеей предоставить свою версию метода.

Leandro Caniglia 06.07.2018 00:02

@LeandroCaniglia спасибо за исправление опечатки :) в startAt :. Это отстой, когда копипаст не работает правильно с SO. Вы, конечно, правы насчет 0, когда ничего не нашли. Я скорректировал код. (У меня был код в рабочей области, и мне пришлось преобразовать его в селектор).

tukan 06.07.2018 08:21

Другие вопросы по теме