String Rotation
January 31, 2012
This is easy if you know the trick, and harder if you don’t. The two strings are rotations of each other if they are the same length and if the one of the strings is contained in the concatenation of the other string with itself:
(define (string-rotated? s1 s2)
(and (= (string-length s1) (string-length s2))
(string-find s2 (string-append s1 s1))))
This function goes beyond the requirement: if one string is a rotation of the other, it tells how many characters must be moved from the beginning to the end of the first string in order to make it the same as the second string.
We used string-find from the Standard Prelude. You can run the program at
Programming Praxis 
In Haskell:
Besser so:
having an easy way to rotate strings in APL, rotating only those amounts that would make the first characters match seemed like a neat little optimization:
isRotation←{1∊⍺∘≡¨(¯1+{⍵/⍳⍴⍵} ⍵=⍬⍴⍺)∘.⌽⊂⍵}
but, the length match test, and the looking within a concatenated pair of the target is much neater, without the messy match and actual rotates.
isRotation2←{~(⍴⍺)≡⍴⍵:0 ⋄ 1∊⍺⍷⍵,⍵}
The written code in C:
#include
#include
#include
int is_rotate(char* str1, char* str2){
int newlen = (strlen(str1) == strlen(str2)) ? 2*strlen(str1) : 0;
if (!newlen)
return 0;
char* str_concat = (char*) malloc( newlen + 1);
strcpy(str_concat, str1);
strcat(str_concat, str1);
str_concat [newlen] = ”;
printf(“String1: %s\n”, str1);
printf(“String2: %s\n”, str2);
printf(“Concats: %s\n\n”, str_concat);
char* substr = strstr(str_concat, str2);
if (!substr)
return 0;
else
return 1;
}
int main() {
char string1[] = “Hi_Amir_How_Are_You_Amir_”;
char string2[] = “How_Are_You_Amir_Amir_Hi_”;
char string3[] = “How_Are_You_Amir_Hi_Amir_”;
printf(“===> Str1 & Str2 Are%s Equal.\n\n”, (is_rotate(string1, string2)) ? “” : ” \”NOT\””);
printf(“===> Str1 & Str3 Are%s Equal.\n\n”, (is_rotate(string1, string3)) ? “” : ” \”NOT\””);
return;
}
Okay, Mr. Programming Praxis – here’s my brute force approach, using PL/SQL. (I should have read your elegant solution first.)
declare s1 constant varchar2(100) := 'ProgrammingPraxis' ; s2 constant varchar2(100) := 'PraxisProgramming' ; stmp varchar2(100) ; begin -- get rid of unequal length strings if length(s1) <> length(s2) then dbms_output.put_line(s1||' is NOT a rotation of '||s2) ; return ; end if ; -- rotate string2 and compare strings stmp := s2 ; for i in 1..length(s1) loop stmp := substr(stmp,2,length(stmp))||substr(stmp,1,1) ; if s1 = stmp then dbms_output.put_line(s1||' is a rotation of '||s2) ; return ; end if ; end loop ; dbms_output.put_line(s1||' is NOT a rotation of '||s2) ; end ; / ProgrammingPraxis is a rotation of PraxisProgrammingHere is one solution in C which does not require memory allocation and string concatenation:
#include <stdio.h> #include <string.h> int is_rotate(const char* str1, const char* str2) { const int len = strlen(str1); if (strlen(str2) == len) { int offset, i; for (offset = 0; offset < len; ++offset) { for (i = 0; i < len; ++i) { if (str1[i] != str2[(i+offset)%len]) break; } if (i==len) return 1; /* found rotation */ } } return 0; } int main(void) { char str1[] = "ProgrammingPraxis"; char str2[] = "PraxisProgramming"; char str3[] = "PraxsiProgramming"; printf("str1 & str2 are%s equal.\n", (is_rotate(str1, str2)) ? "" : " NOT"); printf("str1 & str3 are%s equal.\n", (is_rotate(str1, str3)) ? "" : " NOT"); }Apparently I had the same idea as Georg.
def is_rot(s, t): n = len(s) if len(t) != n: return False for k in range(0, n): ok = True for i, ch in enumerate(s): if ch != t[(i + k) % n]: ok = False break if ok: return True return False if __name__ == "__main__": cases = [ ("ProgrammingPraxis", "PraxisProgramming", True), ("ProgrammingPraxis", "PrasixProgramming", False), ("aab", "aba", True), ("bbaa", "baba", False) ] for c in cases: print("OK" if is_rot(c[0], c[1]) == c[2] else "Fail")THis is how I did in C++, [look amateur]:
#include
#include
using namespace std;
bool isRotateString(string, string);
int main()
{
string s1,s2;
cout <> s1;
cout <> s2;
if ((isRotateString(s1,s2)) == true)
cout << "YES!!!";
else cout <= 0; –i)
{
c = s1[i];
if (s1[i] == toupper(c))
{
rString += s1.substr(i, m – i);
m -= (m – i);
}
}
cout << "Rotated string : " << rString << endl;
if (rString == s2)
return true;
else return false;
}
}
#include <iostream> #include <string> using namespace std; bool isRotateString(string, string); int main() { string s1,s2; cout << "Input string 1: "; cin >> s1; cout << "Input string 2: "; cin >> s2; if ((isRotateString(s1,s2)) == true) cout << "YES!!!"; else cout << "NO!!!"; return 0; } bool isRotateString(string s1, string s2) { //have to be same length at first if (s1.length() != s2.length()) return false; //yeah same length, now what? else { string rString = ""; int i, m = s1.length(); char c; //starting from the very-end for (i = s1.length()-1; i >= 0; --i) { c = s1[i]; if (s1[i] == toupper(c)) { rString += s1.substr(i, m - i); m -= (m - i); } } cout << "Rotated string : " << rString << endl; if (rString == s2) return true; else return false; } }Geez. I had forgotten how painful it is to write in imperative languages, especially when one has to do everything manually!
Language is Ada (because C should be forbidden.)
I used a concatenation approach instead of modulo, for no special reason.
with Ada.Text_IO; with Ada.Command_line; use Ada.Command_Line; procedure Rotate is function RotateF (S1: in String ; S2: in String) return Boolean is FFFOUND : exception; NOPE : exception; S3 : String := S2 & S2; Pos : Integer := 1; Cur : Integer; begin if S1'Length /= S2'Length then return False; end if; for Pos in 1..S1'Length loop Cur := 0; begin while Cur < S1'Length loop if S1(1+Cur) /= S3(Pos+Cur) then raise NOPE; end if; Cur := Cur + 1; end loop; raise FFFOUND; exception when NOPE => null; end; end loop; return(False); exception when FFFOUND => return(True); end RotateF; begin if RotateF(Argument(1),Argument(2)) then Ada.Text_IO.Put_line("tation!Ro"); else Ada.Text_IO.Put_line("Not a rotation!"); end if; end Rotate;Common Lisp FTW \o/
(defun rotatep (s1 s2) (and (= (length s1) (length s2)) (loop for i below (length s1) when (loop for j below (length s1) when (not (char= (aref s1 (mod (+ i j) (length s1))) (aref s2 j))) return nil finally (return t)) return t)))What a cool trick the model answer is. Before seeing it, I thought the problem merely tedious.
Here is an expansive answer, just for fun. (Python 3 it is.)
def is_rotated(s, t): return ( { s[k:] + s[:k] for k in range(len(s)) } == { t[k:] + t[:k] for k in range(len(t)) } )In python, the obvious solution is:
def is_rotation(s1, s2): return s1 in s2+s2An alternative:
import re
def is_rotation(s1, s2):
return any(s1.startswith(s2[i:]) and s1.endswith(s2[:i]) for i in (mo.start() for mo in re.finditer(s1[0], s2)))
Mike: In your first solution, you must also check that the two strings are the same length. Otherwise, you will erroneously report that the two strings are rotations if s1 is a substring of s2.
It appeared to me in the description that the rotation function is based on words in the string and not the string itself, so I wrote a solution that splits the string into words and compares the reverse of the second to the first: http://codepad.org/G1ws5Bu3
It is somewhat generic; allowing the user to pass in a function that interprets whether a given character in the string is a delimiter and whether to include said delimiter as part of the word.
For trivial functions like this I tend to write doctests since they’re pretty quick for getting you started. Documentation also flows a little more naturally with them as you explore the various cases.
hot perl action using OPs wizardry:
sub is_rotation($$) { return length($_[0]) == length($_[1]) && ($_[0] x 2) =~ m/$_[1]/; }simply-C-ty :P
#include<stdio.h> #include<string.h> int main(int argc,char* argv[]) { int i=0,index1=1,index2=1,flag=1; for(;index1<strlen(argv[1]);index1++) if(argv[1][index1]>=65 && argv[1][index1]<=90) break; for(;index2<strlen(argv[2]);index2++) if(argv[2][index2]>=65 && argv[2][index2]<=90) break; for(;i<index1;i++) if(argv[1][i]!=argv[2][index2+i]) flag=0; for(i=0;i<index2;i++) if(argv[2][i]!=argv[1][index1+i]) flag=0; printf("%sString Rotation",strlen(argv[1])!=strlen(argv[2])||flag==0?"Not ":""); }isRotation(String str1,String str2)
//Check lengths
if(length(str1)!=length(str2))
return false
end if
else
//concat the string with itself and check if the concatenated string is a substring of str1
String str3=str2+str2
return str3.contains(str1)
end else
//method in java
public boolean isRotation(String str1,String str2)
{
if(str1.length()!=str2.length())
return false;
else
{
String str3=str2+str2;
return str3.contains(str1);
}
}
I liked Nick’s solution!
Here I’ve tried it to solve using regex in Java.
My first submission!
package raju; import java.util.ArrayList; import java.util.regex.Matcher; import java.util.regex.Pattern; public class RotationalStringMatch { public static void main(String[] args){ String firstString = args[0]; String secondString = args[1]; if(firstString.length() != secondString.length()){ System.out.println("Input String lengths are not matching. Please enter valid strings of same length."); System.exit(0); } ArrayList<String> firstStringSplitList = formSplitStringList(firstString); ArrayList<String> secondStringSplitList = formSplitStringList(secondString); if( (firstStringSplitList.size() > 2) || (secondStringSplitList.size() > 2)) { System.out.println("More than two words in a String. Please check input String"); System.exit(0); } String reverseFirstString = firstStringSplitList.get(1) + firstStringSplitList.get(0); if(reverseFirstString.equals(secondString)) System.out.println("Match found. Both Strings are word reversly equal"); else System.out.println("No match. Words in input strings are different. Give valid input strings!"); } public static ArrayList<String> formSplitStringList(String inputString){ Pattern p = Pattern.compile("[A-Z]{1}[a-z]*"); Matcher m = p.matcher(inputString); ArrayList<String> stringSplitList = new ArrayList<String>(); while(m.find()){ stringSplitList.add(m.group()); } return stringSplitList; } }Using substrings in Java:
public static boolean Stringrot(String s1, String s2){
int cnt = 0;
if(s1.length() !=s2.length()){
return false;
}
while(cnt<s1.length() && s2.contains(s1.substring(0,++cnt))){}
if(s2.contains(s1.substring(cnt-1))){
return true;
}
else{
return false;
}
}
Let the given two strings are string1 and string2. We have to check whether string2 is a rotation of string1. The algorithm works as :
Check the length of the two strings. If they are not same, return false.
Otherwise, concatenate string1 with itself and check whether string2 is a substring of it.
For explanation and code http://www.algoqueue.com/algoqueue/default/view/7208960/check-whether-one-string-is-a-rotation-of-another
@Lal
I have tried both methods. The second method does not work for the word combination “affenzoo” vs. “zooaffen”. (i.e. monkey zoo).
Can you clarify?
Thank you,
http://pastebin.com/60CusEQc