Count of cyclic permutations having XOR with other binary string as 0 | Implementation of Z - algorithm for linear time pattern searching ; Function to get the count of the cyclic permutations of b that given 0 when XORed with a ; concatenate b with b ; new b now contains all the cyclic permutations of old b as it 's sub-strings ; concatenate pattern with text ; Fill z array used in Z algorithm ; pattern occurs at index i since z value of i equals pattern length ; Driver code
def compute_z ( s , z ) : NEW_LINE INDENT l = 0 NEW_LINE r = 0 NEW_LINE n = len ( s ) NEW_LINE for i in range ( 1 , n , 1 ) : NEW_LINE INDENT if ( i > r ) : NEW_LINE INDENT l = i NEW_LINE r = i NEW_LINE while ( r < n and s [ r - l ] == s [ r ] ) : NEW_LINE INDENT r += 1 NEW_LINE DEDENT z [ i ] = r - l NEW_LINE r -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = i - l NEW_LINE if ( z [ k ] < r - i + 1 ) : NEW_LINE INDENT z [ i ] = z [ k ] NEW_LINE DEDENT else : NEW_LINE INDENT l = i NEW_LINE while ( r < n and s [ r - l ] == s [ r ] ) : NEW_LINE INDENT r += 1 NEW_LINE DEDENT z [ i ] = r - l NEW_LINE r -= 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def countPermutation ( a , b ) : NEW_LINE INDENT b = b + b NEW_LINE b = b [ 0 : len ( b ) - 1 ] NEW_LINE ans = 0 NEW_LINE s = a + " $ " + b NEW_LINE n = len ( s ) NEW_LINE z = [ 0 for i in range ( n ) ] NEW_LINE compute_z ( s , z ) NEW_LINE for i in range ( 1 , n , 1 ) : NEW_LINE INDENT if ( z [ i ] == len ( a ) ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = "101" NEW_LINE b = "101" NEW_LINE print ( countPermutation ( a , b ) ) NEW_LINE DEDENT