two strings are rotation of each other or not

miss sophie schrieb:

Here is an idea, not quite sure about correctness though:

0. check whether both strings match in length (obviously)
1. append string1 to string1, i.e. tmpstr = string1.string1
2. return true iff string2 is a substring of tmpstr (can be done in linear time iirc)

Nice. Just found the same

icarus2

miss sophie schrieb:

2. return true iff string2 is a substring of tmpstr (can be done in linear time iirc)

How can this step be executed in linear time? Can anyone describe an algorithm that checks whether s1 is a substring of s2 in linear time?

icarus2 schrieb:

miss sophie schrieb:

2. return true iff string2 is a substring of tmpstr (can be done in linear time iirc)

How can this step be executed in linear time? Can anyone describe an algorithm that checks whether s1 is a substring of s2 in linear time?

http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

icarus2

Tim schrieb:

http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Thx! I somehow confused myself but now I remember

Time nice idea. But u need more memory:) how can we achieve linear complexity without additional memory?

Jester

Well it is not necessary to actually append the string. Just implement the substring test yourself and jump to the front again after the first traversal.

wxSkip

Jester schrieb:

Well it is not necessary to actually append the string. Just implement the substring test yourself and jump to the front again after the first traversal.

But the algorithm needs additional memory...

thats what im talking about...can i achieve linear complexity without additional memory?

wxSkip

Geri1 schrieb:

thats what im talking about...can i achieve linear complexity without additional memory?

> 0, then S[x-1] = S[T[x] - 1]. If you moved the T values one eintry to the left and wrote the T value to the string if it was > 0, it could work (of course you would have to use ASCII codes that aren't used in the string, e.g. values from 128 to 255 or use free character codes if you use a Unicode string).

The other algorithms that were proposed by Wikipedia all needed additional memory and I suppose it will be needed for linear complexity if you don't use tricks.

I found this from here: http://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string

but looks hard to read...

bool is_rotation(const string& str1, const string& str2)
{
  if(str1.size()!=str2.size())
    return false;

  vector<size_t> prefixes(str1.size(), 0);
  for(size_t i=1, j=0; i<str1.size(); i++) {
    while(j>0 && str1[i]!=str1[j])
      j=prefixes[j-1];
    if(str1[i]==str1[j]) j++;
    prefixes[i]=j;
  }

  size_t i=0, j=0;
  for(; i<str2.size(); i++) {
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }
  for(i=0; i<str2.size(); i++) {
    if(j>=str1.size()) return true;
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }

  return false;
}

wxSkip

Geri1 schrieb:

I found this from here: http://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string

This also uses O(n) memory, but someone in the stackoverflow thread said you could use constant memory with the Two Way Algorithm or the SMOA string matching algorithm.