Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

goal is a rotation of s exactly when lengths match and goal appears inside s + s.

Example 1

Input

abcde
cdeab

Output

YES

Example 2

Input

abcde
abced

Output

NO

Hints

  1. Write s twice in a row: s + s contains every rotation of s.
  2. 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");
    }
}

Solve Check String Rotation online · All practice problems