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

Question

Это кажется чрезвычайно простым, но если у меня есть ментальный блок.
У меня есть строка, которая содержит, скажем, только «_» и «х», и мне нужно найти задом позиции всех х-последовательностей:

xxx___xxx___xxx 
___x__xxx_xxx__ 

Какой самый быстрый подход? Должен ли я использовать KMP или BM, или это перебор?

Answer 1

Вы можете сканировать строковое письмо письменно. Вот псевдокод в python:

prev = '' 
# enumerate(collection) enumerates collection elements along with their indices 
# in the form of tuple (index, element) 
# in python strings are collections of characters 
for i, c in enumerate(string): 
    if c == 'x' and c != prev: 
      print "found x sequence at position %d" % i # (this prints out the index) 
    prev = c