2

Надо найти количество подстрок в строке. То есть, сколько раз встретится первая переменная во второй.

input:

aba
ababaa

output:

2

Мой код:

s = input()
n = input()

if s in n:
    print(n.count(s))

Пробовал и регулярным выражением:

import re

s = input()
t = input()

pattern=re.compile(s)
result = re.findall(pattern,t)

print(len(result))
2
  • Используйте регулярное выражение. 24 фев 2021 в 5:54
  • но ответ так же 1 а нужно 2 24 фев 2021 в 5:56

4 ответа 4

3

Доработал Ваше второе решение:

import re

s = 'aba'
t = 'ababaa'

pattern = re.compile('(?=(' + re.escape(s) + '))')

result = pattern.findall(t)
print(len(result))
  • re.escape - экранировать спец-символы регулярных выражений в строке (чтобы корректно обработались всякие ., () и тд);
  • (?=(aba)) - небольшой трюк с positive lookahead, чтобы можно было искать пересекающиеся совпадения. Подробнее можно посмотреть на regular-expressions.info.
1
  • Отличное решение :), кст, мб лучше форматирование добавить: f'(?=({re.escape(s)}))'?
    – gil9red
    24 фев 2021 в 8:24
2

Накидал алгоритм, попробуйте:

s = 'aba'
t = 'ababaa'

indxs = set()
for i in range(len(t)):
    idx = t.find(s, i)
    if idx != -1:
        indxs.add(idx)

print(len(indxs), indxs)
# 2 {0, 2}
2
  • Кажется, можно оптимизировать, начиная следующую итерацию с предыдущего найденного idx?
    – andreymal
    24 фев 2021 в 6:44
  • @andreymal, мб, сделайте отдельным ответом, пожалуйста :)
    – gil9red
    24 фев 2021 в 7:31
2

Или просто проверить, с чего начинается очередной срез:

s = 'aba'
t = 'ababaa'

counter = 0
for i in range(len(t)):
   if t[i:].startswith(s):
      counter += 1

в counter теперь:

>>> print(counter)
2
1

Можно воспользоваться алгоритмом Кнута — Морриса — Пратта. Он позволяет за линейное время найти все подстроки.

# Knuth-Morris-Pratt string matching
# David Eppstein, UC Irvine, 1 Mar 2002

#from http://code.activestate.com/recipes/117214/
def KnuthMorrisPratt(text, pattern):

    '''Yields all starting positions of copies of the pattern in the text.
Calling conventions are similar to string.find, but its arguments can be
lists or iterators, not just strings, it returns all matches, not just
the first one, and it does not need the whole text in memory at once.
Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''

    # allow indexing into pattern and protect against change during yield
    pattern = list(pattern)

    # build table of shift amounts
    shifts = [1] * (len(pattern) + 1)
    shift = 1
    for pos in range(len(pattern)):
        while shift <= pos and pattern[pos] != pattern[pos-shift]:
            shift += shifts[pos-shift]
        shifts[pos+1] = shift

    # do the actual search
    startPos = 0
    matchLen = 0
    for c in text:
        while matchLen == len(pattern) or \
              matchLen >= 0 and pattern[matchLen] != c:
            startPos += shifts[matchLen]
            matchLen -= shifts[matchLen]
        matchLen += 1
        if matchLen == len(pattern):
            yield startPos

Воспользуемся генератором:

result = sum(1 for x in KnuthMorrisPratt('ababaa', 'aba'))

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.