Найти в строке символы в нужной последовательности

По-питонски:

from functools import reduce

def contains(sub, string):
  return reduce(lambda a, c: a + 1 if a < len(sub) and c == sub[a] else a, string, 0) >= len(sub)

Почти, что псевдокод:

def contains(sub, string):
  counter = 0
  for i in string:
    if counter < len(sub) and sub[counter] == i:
      counter += 1
  return counter == len(sub)

Наиболее эффективный вариант:

def contains(sub, string):
  counter = 0
  for i in string:
    if sub[counter] == i:
      counter += 1
      if counter == len(sub): return True
  return False

print(contains('xyz', 'axbycz'))  # True
print(contains('xyz', 'axbcz'))   # False
print(contains('aa', 'axbcz'))    # False

def contains(pattern, string):
    pattern = list(pattern[::-1])
    for char in string:
        if char == pattern[-1]:
            pattern.pop()
            if len(pattern) == 0: return True
    return False

Если образец (p) заметно короче чем текст (s), то этот вариант показывает лучшую производительность. Если их длина почти равна, то лучшее решение в другом ответе.

Три хитрости:

• цикл по образцу требует меньше итераций чем цикл по строке;
• функция si экономит время в цикле (оператор . требует времени и это заметно);
• условие выхода не проверяется отдельно в каждой итерации, вместо этого обработка исключения.

Код:

def match(p, s):
    i = 0
    si = s.index
    try:
        for c in p:
            i = si(c, i) + 1
    except ValueError:
        return False
    return True

def contains(sub, stri):
    sub = iter(sub)
    sb = next(sub)
    for s in stri:
        if s == sb:
            try: sb = next(sub)
            except StopIteration: return True
    return False

print(contains('xyz', 'yyzxxxzyyyxzyyx'))  # True
print(contains('xyz', 'axbycz'))  # True
print(contains('xyz', 'axbcz'))   # False
print(contains('aa', 'axbcz'))    # False