13366

26
+177  Q:

## Interview question: Check if one string is a rotation of other string.

+448  A:

You can do:

• First make sure `s1` and `s2` are of the same length.
• Check to see if `s2` is a `substring` of `s1 concatenated with s1`.

.

``````algorithm checkRotation(string s1, string s2)
if( len(s1) != len(s2))
return false
if( substring(s2,concat(s1,s1))
return true
return false
end
``````

In Java:

``````boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}
``````
+1 Nice!.......
That's very nice. +1.
AHA! +1 (adding characters to fit minimum comment size)
don't you mean: substring(s2,concat(s1,s1)?
@yaneeve: Thanks for pointing.
Thats pretty simple.
+1 very clever!
@codadict: Thank you sir for the clever solution.
@Juliet: No it would return false as "flarg" is not a substring of "blargblarg"
Beautiful. In Python it's really neat; two lines.
Very nice. What I like most is that your answer is actually a good way of defining "is a rotation of". As a sidenote, you could also write "return len(s1) == len(s2) ", but that's not necessarily better style, especially for such a short function.
I like its elegance, but I had to think for a while to check there weren't any false positives. (I don't *think* there are.)
Nice solution. Stupid interview question.
@Jon, @codaddict, if the same string is not considered a rotation, then all solutions on this page support false positives. That would be a good question to ask the interviewer, as well as if you are bounded by memory.
What the point of this solution? It's like saying "blah, my language has a function checkRotation()" and I'll use that. substring() is doing all the work.
You can also use `(s1+s1).contains(s2)` in Java.
@MK1 : Interview question such as these are usually used to check how the person would tackle a problem.
+1 - very neat solution
Since it is a "how would you" question, not "what is a good algorithm to", this answer is appropriate. Otherwise, this would just be an innuendo for the follow up question "and how does that work?".
Anyway I would object a bit to this as an interview question. It has an "aha!" component, I think. Most programmers (me included) would just use brute force, which is not unreasonable anyway, and that may feel like not "clever" enough to the interviewer.
surely its `s1 + s1.substring(0, s1.length() - 1)` as the concatenation?
+1 Clever indeed.
Elegant and Clever
@Jon Concentrate on `s1+s1`. Clearly, all of its substrings with size `s1.length` are rotations of `s1`, by construction. Therefore, any string of size `s1.length` that is a substring of `s1+s1` must be a rotation of `s1`.
+1 brilliant solution
I like checking the length first. An optimization to be sure, but simple, efficient and preventing possible false positives.
@unicornaddict - what's great about this solution is it's so obvious once you point it out, I hate myself for not thinking of it!
@extraneon: It's necessarry to check the length first, otherwise you get a false positive if s1 is a substring of s2. Given s2 = "Hello", s1="Hello World", then s2 is a substring of s1+s1, but s1 is not a rotation of s2.
+1: One one hand I'm quite pleased, this is exactly how I would have answered this question, on the other hand I feel slightly ill at the thoughts of 3k+ rep I could have reaped if I'd been first on the scene. Well done unicornaddict :)
It would be excellent if anybody could print a proof?
Very nice solution
+1, good answer. Can it be done without allocating new memory?
I am curious though if we were to define 'is a rotation of' as function(or "operation") of String. Apparently it is commutative, i.e if s1 is a rotation of s2 then s2 is a rotation of s1. The answer covers this as well. Now, what if let's say, a String cannot be a rotation of itself, then we may have to add one more checking. Actually, even if a String _can_ be a rotation of itself, a checking on s1.equals(s2) would skip the concat part. An improvement performance wise maybe?
+18  A:

EDIT: The accepted answer is clearly more elegant and efficient than this, if you spot it. I left this answer as what I'd do if I hadn't thought of doubling the original string.

I'd just brute-force it. Check the length first, and then try every possible rotation offset. If none of them work out, return false - if any of them does, return true immediately.

There's no particular need to concatenate - just use pointers (C) or indexes (Java) and walk both along, one in each string - starting at the beginning of one string and the current candidate rotation offset in the second string, and wrapping where necessary. Check for character equality at each point in the string. If you get to the end of the first string, you're done.

It would probably be about as easy to concatenate - though probably less efficient, at least in Java.

+1 - we don't need no elegant solutions that run in 3+ times the most efficient solution. This is C ... micro-optimization is *de riguer*.
As this comes has come up before on stackoverflow, searching from the end of the string to the beginning provides a jumping mechanism which can greatly increase the speed of substring searches. Because of this, I would argue that it isn't much faster to run this in place, particularly with a brute force forward searching solution.
Interviewer: Lotta talk, but I bet this guy can't code.
@NickLarsen: I'm afraid I don't quite understand your comment. What exactly are you suggesting?
@Beau: If anyone wants to think that, they're welcome to ask me for code. If someone just asks me "how I would do something" I usually describe the algorithm rather than leaping to code.
@Jon - I read Beau's comment as being a joke
@oxbow_lakes: Possibly. It's hard to tell.
@Jon Skeet There is a substring finding algorithm which searches from the end of the string to the front (http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm) which has a smaller coefficient than forward searching. You could implement it without the concatenation for this problem, but my point is that the elegant answer is on same magnitude of efficiency as what you suggest.
@Jon It was a joke! The interviewer doesn't interview Jon Skeet, Jon Skeet interviews him.
@NickLarsen: The elegant answer is certainly the way to go when you've spotted the trick. My answer is what I'd probably actually give in an interview though, if I didn't know the trick. I certainly wouldn't start implementing a complicated substring algorithm.
@Jon: that would be interesting to check efficiency of both implementations, my bet is that concatenating string is probably *more* efficient that the direct pointer solution, at least if you don't optimize the implementation for an unreasonable amount of time, even in Java. My rationale is that for the trivial solution you would call very simple heavily optimized library functions.
@kriss Jon's solution has O(n^2) worst case, so it's hardly a question which of them is faster.
+41  A:

Another python example (based on THE answer):

``````def isrotation(s1,s2):
return len(s1)==len(s2) and s1 in 2*s2
``````
Interestingly I thought of duplicated `s2` rather than `s1` too... then realized that the relation was symmetric anyway.
If the string could be long, here's a Python version that uses Boyer-Moore to get O(n) running time: def isrotation(s1, s2): return len(s1)==len(s2) and re.compile(re.escape(s1)).search(2*s2) is not None
@Duncan: does the `in` operator not use an O(n) algorithm?
The running time of the 'in' operator depends on the length of both strings. Consider `a in b` where `a` is `xxxxxxz` and b is a lot of x's: At best Python will compare len(b)-len(a) starting positions (I'm not sure here, it might just do len(b) comparisons) and len(a)-1 character comparisons from each location. Regular expressions with constant prefixes on the other hand do fewer comparisons (complicated to work out but apparently O(n) and often a lot fewer).
+6  A:
Ah, C. Why do something in half the time and code when you can do it in C!
+1 It's very well written C. And to be fair, the question is tagged 'c'.
In this code you have walked the strings at least 2 if not 3 times (in strlen and strcmp). You can save yourself this check and you can keep that logic in your loop. As you are looping, if one string character count is different than the other, exit the loop. You will know the lengths, as you know the start and you know when you've hit the null terminator.
@Beau Martinez - because sometimes execution time is more important than development time :-)
@phkahler - The thing is it might well be slower. The built in index functions in the other languages typically use a fast string search algorithm like Boyer-Moore, Rabin-Karp or Knuth-Morris-Pratt. It is too naive just reinvent everything in C, and assume it to be faster.
+14  A:

Here's one using regex just for fun:

``````boolean isRotation(String s1, String s2) {
return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}
``````

You can make it a bit simpler if you can use a special delimiter character guaranteed not to be in either strings.

``````boolean isRotation(String s1, String s2) {
// neither string can contain "="
return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}
``````

You can also use lookbehind with finite repetition instead:

``````boolean isRotation(String s1, String s2) {
return (s1 + s2).matches(
String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
);
}
``````
+1 for being a regex master.
-1 For putting the words "regex" and "fun" in the same statement, without modifying "fun" with "not" (only joking, I didn't down vote)
-3 for implying that regexes aren't fun.
+16  A:

As others have submitted quadratic worst-case time complexity solution, I'd add a linear one (based on the `KMP Algorithm`):

``````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;
}
``````

working example

+1 for ideone.com - it looks very interesting!
+54  A:

Surely a better answer would be, "Well, I'd ask the stackoverflow community and would probably have at least 4 really good answers within 5 minutes". Brains are good and all, but I'd place a higher value on someone who knows how to work with others to get a solution.

+1 for sheer cheek. Made my day :-)
If they disagreed, you could then link them to this question.
Whipping out your cellphone during an interview might be considered rude and in the end they'd end up hiring Jon Skeet.
Thats actually probably exactly what I would have said
I don't think they will be able to afford Jon Skeet.
+2  A:

Opera's simple pointer rotation trick works, but it is extremely inefficient in the worst case in running time. Simply imagine a string with many long repetitive runs of characters, ie:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

The "loop until there's a mismatch, then increment by one and try again" is a horrible approach, computationally.

To prove that you can do the concatenation approach in plain C without too much effort, here is my solution:

``````  int isRotation(const char* s1, const char* s2) {
assert(s1 && s2);

size_t s1Len = strlen(s1);

if (s1Len != strlen(s2)) return 0;

char s1SelfConcat[ 2 * s1Len + 1 ];

sprintf(s1SelfConcat, "%s%s", s1, s1);

return (strstr(s1SelfConcat, s2) ? 1 : 0);
}
``````

This is linear in running time, at the expense of O(n) memory usage in overhead.

(Note that the implementation of strstr() is platform-specific, but if particularly brain-dead, can always be replaced with a faster alternative such as the Boyer-Moore algorithm)

Do you know of any platform that has `strstr()` in O(n+m)? Also, if the standard (or anything else) doesn't guarantee you a linear running time of `strstr()`, you cannot assert that the whole algorithm has linear time compexity.
Which is why I said that it can be replaced by the Boyer-Moore algorithm, making it run in linear time.
There are a couple of potential problems with your method of allocating `s1SelfConcat`: it's only since C9x that C allows variable array sizes (although GCC has allowed it much longer), and you will run into trouble allocating large strings on the stack. Yosef Kreinin wrote [a very amusing blog post](http://www.yosefk.com/blog/the-c-sucks-series-petrifying-functions.html) about this problem.Also, your solution is still quadratic time with Boyer-Moore; you want KMP.
+3  A:

Nobody offered a modulo approach yet, so here's one:

``````static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));
}

public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);

if (b.Length != a.Length)
return false;

int ndx = a.IndexOf(b[0]);
bool isRotation = true;
Console.WriteLine("Ndx: {0}", ndx);
if (ndx == -1) return false;
for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];

Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );

if (b[i] != rotatedA)
{
isRotation = false;
// break; uncomment this when you remove the Console.WriteLine
}
}
return isRotation;
}
``````

Output:

``````A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False
``````

[EDIT: 2010-04-12]

piotr noticed the flaw in my code above. It errors when the first character in the string occurs twice or more. For example, `stackoverflow` tested against `owstackoverflow` resulted in false, when it should be true.

Thanks piotr for spotting the error.

Now, here's the corrected code:

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestRotate
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "tackoverflwos"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));

}

public static bool IsRotation(string a, string b)
{
Console.WriteLine("\nA: {0} B: {1}", a, b);

if (b.Length != a.Length)
return false;

if (a.IndexOf(b[0]) == -1 )
return false;

foreach (int ndx in IndexList(a, b[0]))
{
bool isRotation = true;

Console.WriteLine("Ndx: {0}", ndx);

for (int i = 0; i < b.Length; ++i)
{
int rotatedNdx = (i + ndx) % b.Length;
char rotatedA = a[rotatedNdx];

Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);

if (b[i] != rotatedA)
{
isRotation = false;
break;
}
}
if (isRotation)
return true;
}
return false;
}

public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}

}//class Program
}//namespace TestRotate
``````

Here's the output:

``````A: stackoverflow B: ztackoverflow
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True
``````

Here's the lambda approach:

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsRotation
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ztackoverflow"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "ackoverflowst"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "overflowstack"));
Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "stackoverflwo"));

Console.WriteLine("Rotation : {0}",
IsRotation("stackoverflow", "owstackoverfl"));

string strToTestFrom = "stackoverflow";
foreach(string s in StringRotations(strToTestFrom))
{
Console.WriteLine("is {0} rotation of {1} ? {2}",
s, strToTestFrom,
IsRotation(strToTestFrom, s) );
}
}

public static IEnumerable<string> StringRotations(string src)
{
for (int i = 0; i < src.Length; ++i)
{
var sb = new StringBuilder();
for (int x = 0; x < src.Length; ++x)
sb.Append(src[(i + x) % src.Length]);

yield return sb.ToString();
}
}

public static bool IsRotation(string a, string b)
{
if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
foreach(int ndx in IndexList(a, b[0]))
{
int i = ndx;
if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
return true;
}
return false;
}

public static IEnumerable<int> IndexList(string src, char c)
{
for (int i = 0; i < src.Length; ++i)
if (src[i] == c)
yield return i;
}

}//class Program

}//namespace IsRotation
``````

Here's the lambda approach output:

``````Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True
``````
I don't think your answer is correct since int ndx = a.IndexOf(b[0]); will work only if there are not other elements with the same value of b[0] in the string.
thanks for noticing the flaw. corrected it now
A:
``````int rotation(char *s1,char *s2)
{
int i,j,k,p=0,n;
n=strlen(s1);
k=strlen(s2);
if (n!=k)
return 0;
for (i=0;i<n;i++)
{
if (s1[0]==s2[i])
{
for (j=i,k=0;k<n;k++,j++)
{
if (s1[k]==s2[j])
p++;
if (j==n-1)
j=0;
}
}
}
if (n==p+1)
return 1;
else
return 0;
}
``````
+7  A:

I guess its better to do this in `Java`:

``````boolean isRotation(String s1,String s2) {
return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}
``````

In Perl I would do:

``````sub isRotation {
my(\$string1,\$string2) = @_;
return length(\$string1) == length(\$string2) && (\$string1.\$string1)=~/\$string2/;
}
``````

or even better using the index function instead of the regex:

``````sub isRotation {
my(\$string1,\$string2) = @_;
return length(\$string1) == length(\$string2) && index(\$string2,\$string1.\$string1) != -1;
}
``````
You forgot `\Q` in `/\Q\$string2/`.
Why would I use it ?
`\Q` quotes any special characters in `\$string2`. Without it, `.` would be considered to be a rotation of any 1-character string.
A:

have `O(n*n)` complexity.

for every element

``````  rotate s1 by 1 .complexity O(n)

compare with s2 .complexity O(1)

done
``````
How do you compare two strings of length n in O(1) time?
@Thomas, the comparison isn't the problem (even recording it correctly is just O(n), not changing the inside of the loop). That he repeats the O(n) in the rotate for each element makes his algorithm O(n*n).
@Andrew, you are right i am using 2 loops. 2nd for rotationThanks.
A:

To make the algorithm faster we can consider dropping the test of string length. Oops I get it now length comparison is compulsory.

The algorithm needs the strings to be of equal lengths to work, or it will accept invalid inputs. ex) `("stack", "ackoverflowst")` gives `"stack" in "ackoverflowstackoverflowst"` which is true, but shouldn't be.
+1  A:

Another Ruby solution based on the answer:

``````def rotation?(a, b); a.size == b.size and (b*2)[a]; end
``````
+5  A:

Not sure if this is the most efficient method, but it might be relatively interesting: the the Burrows-Wheeler transform. According to the WP article, all rotations of the input yield the same output. For applications such as compression this isn't desirable, so the original rotation is indicated (e.g. by an index; see the article). But for simple rotation-independent comparison, it sounds ideal. Of course, it's not necessarily ideally efficient!

Since the Burrows-Wheeler transform involves computing all rotations of the string, it's surely not going to be optimal.. :-)
+2  A:

C#:

``````s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)
``````
+3  A:

Whoa, whoa... why is everyone so thrilled with an `O(n^2)` answer? I'm positive that we can do better here. THE answer above includes an `O(n)` operation in an `O(n)` loop (the substring/indexOf call). Even with a more efficient search algorithm; say `Boyer-Moore` or `KMP`, the worst-case is still `O(n^2)` with duplicates.

A `O(n)` randomized answer is straightforward; take a hash (like a Rabin fingerprint) that supports an `O(1)` sliding window; hash string 1, then hash string 2, and proceed to move the window for hash 1 around the string and see if the hash functions collide.

If we imagine the worst case being something like "scanning two strands of DNA", then the probability of collisions goes up, and this probably degenerates to something like `O(n^(1+e))` or something (just guessing here).

Finally, there's a deterministic `O(nlogn)` solution that has a very big constant outside. Basically, the idea is to take a convolution of the two strings. The max value of the convolution will be the rotation difference (if they are rotated); an `O(n)` check confirms. The nice thing is that if there are two equal max values, then they are both also valid solutions. You can do the convolution with two FFT's and a dot product, and an iFFT, so `nlogn + nlogn + n + nlogn + n == O(nlogn)`.

Since you can't pad with zeroes, and you can't guarantee that the strings are of 2^n length, the FFTs won't be the fast ones; they'll be the slow ones, still `O(nlogn)` but a much bigger constant than the CT algorithm.

All that said, I'm absolutely, 100% positive that there is a deterministic `O(n)` solution here, but darned if I can find it.

KMP on the concatenated-with-itself string (either physically or virtually with a `%stringsize`) is guaranteed to be linear time.
+1 for Rabin-Karp. Unlike KMP, it uses constant space, and it's simpler to implement. (It's also the first answer I thought of, in seconds, making it hard to see the 'right' answer, because this one's right there and it's sweet.)Your convolution idea reminds me of Shor's algorithm -- I wonder if there's a sublinear quantum solution -- but that's getting silly now, right?
RK does not give a deterministic O(n) solution, and KMP is O(n) in space which might be undesirable. Look up Two Way or SMOA substring searching which are both O(n) in time and O(1) in space. By the way, glibc strstr uses Two Way, but if you actually concatenate strings to use it as opposed to using %len you're back to O(n) in space. :-)
A:

Why not something like this?

``````
//is q a rotation of p?
bool isRotation(string p, string q) {
string table = q + q;
return table.IndexOf(p) != -1;
}
``````

Of course, you could write your own IndexOf() function; I'm not sure if .NET uses a naive way or a faster way.

Naive:

``````
int IndexOf(string s) {
for (int i = 0; i < this.Length - s.Length; i++)
if (this.Substring(i, s.Length) == s) return i;
return -1;
}
``````

Faster:

``````
int IndexOf(string s) {
int count = 0;
for (int i = 0; i < this.Length; i++) {
if (this[i] == s[count])
count++;
else
count = 0;
if (count == s.Length)
return i - s.Length;
}
return -1;
}
``````

Edit: I might have some off-by-one problems; don't feel like checking. ;)

A:

@user309751: we cannot drop the check of length. If we do so it will say bc is rotation of abc.

+2  A:

As no one has given a C++ solution. here it it:

``````bool isRotation(string s1,string s2) {

string temp = s1;
temp += s1;
return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}
``````
+1  A:

I like THE answer that checks if s2 is a substring of s1 concatenated with s1.

I wanted to add an optimization that doesn't lose its elegance.

Instead of concatenating the strings you can use a join view (I don't know for other language, but for C++ Boost.Range provide such kind of views).

As the check if a string is a substring of another has linear average complexity (Worst-case complexity is quadratic), this optimization should improve the speed by a factor of 2 in average.

+2  A:

A pure Java answer (sans null checks)

``````private boolean isRotation(String s1,String s2){
if(s1.length() != s2.length()) return false;
for(int i=0; i < s1.length()-1; i++){
s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
//--or-- s1 = s1.substring(1) + s1.charAt(0)
if(s1.equals(s2)) return true;
}
return false;
}
``````
+2  A:

Here is an `O(n)` and in place alghoritm. It uses `<` operator for the elements of the strings. It's not mine of course. I took it from here (The site is in polish. I stumbled upon it once in the past and I couldn't find something like that now in English, so I show what I have :)).

``````bool equiv_cyc(const string &u, const string &v)
{
int n = u.length(), i = -1, j = -1, k;
if (n != v.length()) return false;

while( i<n-1 && j<n-1 )
{
k = 1;
while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
if (k>n) return true;
if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
}
return false;
}
``````
A:

I'd do this in Perl:

``````sub isRotation {
return length \$_[0] == length \$_[1] and index(\$_[1],\$_[0],\$_[0]) != -1;
}
``````
+1  A:

It's very easy to write in PHP using `strlen` and `strpos` functions:

``````function isRotation(\$string1, \$string2) {
return strlen(\$string1) == strlen(\$string2) && ((\$string1.\$string1).strpos(\$string2) != -1);
}
``````

I don't know what `strpos` uses internally, but if it uses KMP this will be linear in time.

+1  A:

And now for something completely different.

If you want a really fast answer in some constrained context when strings are not rotation of one another

• compute some character based checksum (like xoring all characters) on both strings. If signatures differ strings are not rotations of one another.

Agreed, it can fail, but it is very fast to say if strings don't match and if they match you can still use another algorithm like string concatenation to check.