Как найти повторяющееся слово в строке?

Question

[Артем Чеботарев]

Есть строка - 'HELLOHELLOHELLOHEL'
Каким образом возможно извлечь из этой строки повторяющееся слово?
Половину дня думаю над этим вопросом - и никак не могу придумать что-то дельное.

Comments

[Александр Ручкин]

Уточните условия. Строка всегда вида '...'? Или в ней могут быть другие вставки?

[Александр Ручкин]

Съело пример: строка вида 'WORDWORDWORDWO...'?

[Mrrl]

Какая длина строки? Какая сложность требуется? O(N), O(N*log(N)), или хватит O(N^2)?

[Артем Чеботарев]

Строка всегда содержит одно слово, повторяющееся без пробелов. Строка произвольной длины. Строка может заканчиваться как на само слово полностью, так и на слово, без некоторого количества букв в конце(это количество неизвестно).

Answer 1

[Армянское Радио]

Эту задачу решает Алгоритм Ландау-Шмидта

Answer 2

[Andrey Dugin]

def find_word(line):
    for step in xrange(1, len(line)):
        for start in xrange(step):
            if len(set(line[(start or None)::step])) != 1:
                break
        else:
            return line[:step]
    return line

print find_word('HELLOHELLOHELLOHEL')
print find_word('HHHELLOHHHELLOHHHELLOHHH')
print find_word('_HHELLOHHELLOHHELLOHHELLOHHELLOHHE')

Результат:

HELLO
HHHELLO
_HHELLOHHELLOHHELLOHHELLOHHELLOHHE

Answer 3

[Mrrl]

Попробуйте алгоритм Кнута — Морриса — Пратта. Если с его помощью найти строку в самой себе, то ответом будет как раз сдвиг на повторяющееся слово. Но придётся повозиться с таблицей побочных переходов.

В общем, получается вот такой простой алгоритм (правда, на C++):

int maxrepword(char *A){
	int *ref=new int[strlen(A)];
	int b=0,s=1;
	ref[0]=-1;
	while(A[s]){
		if(A[s]==A[b]) ref[s++]=b++;
		else if(b==0) ref[s++]=-1;
		else b=ref[b-1]+1;
	}
	delete[] ref;
	return s-b;
}

Возвращает длину искомого слова. Время работы - линейное.

Answer 4

[Spetros]

не могу придумать что-то дельное

Ну так приведите тот алгоритм который получился, задайте вопросы по проблемным местам.

Сейчас ваш вопрос выглядит так, как будто глупый и нерадивый студент хочет чтобы за него лабу на питоне написали.

Comments

[Артем Чеботарев]

Я извиняюсь, если это прозвучало именно так. Программирование закончилось уже как год. Сейчас я просто решил начать изучать питон. Тем более сейчас сессия идет, какие лабораторные работы?)

Если честно, даже приводить нечего, потому что вся проблема заключается в том, что про это слово ничего неизвестно, за исключением того, что оно присутствует в строке, поэтому все мои потуги в этом направлении заранее были обречены.

[ManWithBear]

Артем Чеботарев: строка состоит только из этого слова? Или может быть пример "арараСЛОНаврыСЛОНСЛОНавывСЛОН"?

[Артем Чеботарев]

ManWithBear: только из этого слова

[Mrrl]

А в случае WORDWO слово WORD считается повторяющимся? Задача в том, чтобы найти самый короткий период последовательности букв?

[Артем Чеботарев]

Mrrl: да, строка всегда начинает с этого слова.

[Артем Чеботарев]

masolit: извиняюсь, не сразу увидел. Ваш вариант тоже хороший. И я не говорил, что он мне не понравился :)
Спасибо!

Answer 5

[ldv]

str = "HHELLOHHELLOHHELLOHHELLOHHELLOHHE"
word = ""
resword = ""
found = False 

print 'String: ' + str

for i in range(len(str)/2):

   word += str[i]
   print 'Testing subword: ' + word

   found = True
   wordlen = len(word)

   for k in range(len(str)):

      if str[k] != word[k % wordlen]:
         found = False
         print str[k] + ' != '  + word[k % wordlen]
         break
      else:
         print str[k] + ' == '  + word[k % wordlen]

   if found == True:
      resword = word
      break

if found:
   print 'Found: ' + resword
else:
   print 'Found: ' + str

Предыдущая версия работала неверно, спасибо SilentFl за указание на ошибку

Comments

[SilentFl]

еще раз "прикопаюсь": что будет для str = "_HHELLOHHELLOHHELLOHHELLOHHELLOHHE"? :-D
в этом случае надо делать еще один цикл, i для начальной позиции, j для конечной позиции, и k для поиска слова str[i:j] в оставшейся подстроке. Сложность O(n^3), что применимо только для небольших строк, и крест на этом методе

[ldv]

SilentFl: по условию задачи в строке может быть только повторяющееся слово, насколько я понимаю.

[Артем Чеботарев]

Спасибо! Вместо print 'Not found' нужно print str, т.к. по условию слово точно есть в строке, и если оно не найдено, то сама строка и есть это слово.