We are given two strings,AandB.

A_shift onA_consists of taking stringAand moving the leftmost character to the rightmost position. For example, ifA = 'abcde', then it will be'bcdea'after one shift onA. ReturnTrueif and only ifAcan becomeBafter some number of shifts onA.

Example 1:
Input:
 A = 'abcde', B = 'cdeab'

Output:
 true


Example 2:
Input:
 A = 'abcde', B = 'abced'

Output:
 false

Note:

• A and B will have length at most 100 .

n^2

class Solution {
    public boolean rotateString(String A, String B) {
        return A.length() == B.length() && (A + A).contains(B);
    }
}

n

import java.math.BigInteger;
class Solution {
    public boolean rotateString(String A, String B) {
        if (A.equals(B)) return true;

        int MOD = 1_000_000_007;
        int P = 113;
        int Pinv = BigInteger.valueOf(P).modInverse(BigInteger.valueOf(MOD)).intValue();

        long hb = 0, power = 1;
        for (char x: B.toCharArray()) {
            hb = (hb + power * x) % MOD;
            power = power * P % MOD;
        }

        long ha = 0; power = 1;
        char[] ca = A.toCharArray();
        for (char x: ca) {
            ha = (ha + power * x) % MOD;
            power = power * P % MOD;
        }

        for (int i = 0; i < ca.length; ++i) {
            char x = ca[i];
            ha += power * x - x;
            ha %= MOD;
            ha *= Pinv;
            ha %= MOD;
            if (ha == hb && (A.substring(i+1) + A.substring(0, i+1)).equals(B))
                return true;

        }
        return false;
    }
}