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

Question

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

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