two strings are rotation of each other or not

Hi,

How can i check whether the two strings are rotation of each other or not.
Example: str1="SecretPassword" str2="wordSecretPass"

my solution is complexity N*M. how could i improve that to linear complexity?

what happens if i have: "AbbaBabbaAbbaBabba" vs. "BabbaAbbaBabbaAbba" ?

bool is_string_rotated(string str1, string str2) {
	int char_matches = 0;
	int length = 0;

	if(str1.length() != str2.length()) 
		return false;

	length = str1.length();

	for(int i = 0; i < length; i++) {
		char_matches = 0;

		for(int j = 0; j < length; j++) {
			if(str1[j] == str2[(j+i) % length])
				char_matches++;
		}

		if(length == char_matches)
			return true;
	}

	return false;
}

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

SeppJ

I moved this thread to the general programming forum as the question for the algorithm is not specifically related to C++.

On the top of my head I do not know a better solution. Sounds like a standard problem - I would try googling it. Have you done that already?

Nexus

Sort both strings and compare them? Complexity O(n * log n)

Ah, you mean "rotate" and not "permute", sorry.

Nexus schrieb:

Sort both strings and compare them? Complexity O(n * log n)

Ah, you mean "rotate" and not "permute", sorry.

Can still be used to rule out false cases. Would of course not improve worst case complexity.

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)

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.