How to find a repeated word in a string?

Question

Python

There is a string - 'HELLOHELLOHELLOHEL'
How is it possible to extract a repeated word from this string?
I've been thinking about this question for half a day - and I just can't come up with something sensible.

Answer 1

This problem is solved by the Landau-Schmidt algorithm

Answer 2

Try the Knuth-Morris-Pratt algorithm . If you use it to find a string in itself, then the answer will be just a shift to a repeated word. But you have to tinker with the table of side transitions.
In general, this is a simple algorithm (though in 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;
}

Returns the length of the searched word. The running time is linear.

Answer 3

I can't think of anything useful

Well, bring the algorithm that turned out, ask questions on problem areas.
Now your question looks like a stupid and negligent student wants a python lab to be written for him.

Answer 4

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

The previous version did not work correctly, thanks to SilentFl for pointing out the error