Practice › Strings
Check String Rotation
Easy · Strings · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Print YES if goal can be obtained by rotating s (moving some characters from the front to the back), otherwise NO.
Input
Two lines: s and goal.
Output
YES or NO.
Constraints
- 1 ≤ |s|, |goal| ≤ 10^5
goalis a rotation ofsexactly when lengths match andgoalappears insides + s.
Example 1
Input
abcde cdeab
Output
YES
Example 2
Input
abcde abced
Output
NO
Hints
- Write s twice in a row: s + s contains every rotation of s.
- So goal is a rotation exactly when the lengths match and goal is a substring of s + s. Use KMP for a guaranteed linear search.
Approach
Every rotation of s is a window of length |s| inside s + s. If the lengths differ the answer is NO. Otherwise search for goal in s + s. Built-in find/indexOf can be O(n·m) on inputs like "aaaa…ab", so the C++ and Java versions use KMP. KMP matches the text against goal and uses a failure table to avoid re-reading characters.
Complexity: O(n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
// true if pattern p occurs in text t (Knuth–Morris–Pratt)
bool contains(const string &t, const string &p) {
int m = p.size();
vector<int> fail(m, 0);
for (int i = 1, k = 0; i < m; i++) {
while (k > 0 && p[i] != p[k]) k = fail[k - 1];
if (p[i] == p[k]) k++;
fail[i] = k;
}
for (int i = 0, k = 0; i < (int)t.size(); i++) {
while (k > 0 && t[i] != p[k]) k = fail[k - 1];
if (t[i] == p[k]) k++;
if (k == m) return true;
}
return false;
}
int main() {
string s, goal;
cin >> s >> goal;
bool ok = s.size() == goal.size() && contains(s + s, goal);
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}Python solution
s = input().strip()
goal = input().strip()
print("YES" if len(s) == len(goal) and goal in s + s else "NO")Java solution
import java.util.*;
public class Main {
// true if pattern p occurs in text t (Knuth–Morris–Pratt)
static boolean contains(String t, String p) {
int m = p.length();
int[] fail = new int[m];
for (int i = 1, k = 0; i < m; i++) {
while (k > 0 && p.charAt(i) != p.charAt(k)) k = fail[k - 1];
if (p.charAt(i) == p.charAt(k)) k++;
fail[i] = k;
}
for (int i = 0, k = 0; i < t.length(); i++) {
while (k > 0 && t.charAt(i) != p.charAt(k)) k = fail[k - 1];
if (t.charAt(i) == p.charAt(k)) k++;
if (k == m) return true;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(), goal = sc.next();
boolean ok = s.length() == goal.length() && contains(s + s, goal);
System.out.println(ok ? "YES" : "NO");
}
}