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

Есть строка - 'HELLOHELLOHELLOHEL'
Каким образом возможно извлечь из этой строки повторяющееся слово?
Половину дня думаю над этим вопросом - и никак не могу придумать что-то дельное.
  • Вопрос задан
  • 11102 просмотра
Решения вопроса 2
gbg
@gbg Куратор тега Программирование
Любые ответы на любые вопросы
Эту задачу решает Алгоритм Ландау-Шмидта
Ответ написан
Комментировать
adugin
@adugin Куратор тега Python
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
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
Mrrl
@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;
}

Возвращает длину искомого слова. Время работы - линейное.
Ответ написан
Комментировать
Spetros
@Spetros
IT-шник
не могу придумать что-то дельное

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

Сейчас ваш вопрос выглядит так, как будто глупый и нерадивый студент хочет чтобы за него лабу на питоне написали.
Ответ написан
@ldvldv
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 за указание на ошибку
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы