package Leetcode;

import java.math.BigInteger;

/**

* @author szh

* @create 2018-08-16 22:48

**/

public class RotateString {

public boolean rotateString(String A, String B) {

String C = A +A ;

for(int i =0 ;i< C.length() ;i++){

int index =i;

int j=0;

for(;j<B.length() ;j++){

if(C.charAt(index) == B.charAt(j)){

index++;

}else{

break;

}

}

if( j == B.length() ){

return true;

}

}

return false;

}

public boolean rotateStringHash(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;

}

public static void main(String[] args) {

System.out.println(new RotateString().rotateStringHash("abcde", "abced"));

}

}