Count of cyclic permutations having XOR with other binary string as 0 | C # program to find bitwise XOR between binary string A and all the cyclic permutations of binary string B ; 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
using System ; class GFG { public static void compute_z ( string s , int [ ] z ) { int l = 0 , r = 0 ; int n = s . Length ; for ( int i = 1 ; i <= n - 1 ; i ++ ) { if ( i > r ) { l = i ; r = i ; while ( r < n && s [ r - l ] == s [ r ] ) { r ++ ; } z [ i ] = r - l ; r -- ; } else { int k = i - l ; if ( z [ k ] < r - i + 1 ) { z [ i ] = z [ k ] ; } else { l = i ; while ( r < n && s [ r - l ] == s [ r ] ) { r ++ ; } z [ i ] = r - l ; r -- ; } } } } public static int countPermutation ( string a , string b ) { b = b + b ; b = b . Substring ( 0 , b . Length - 1 ) ; int ans = 0 ; string s = a + " $ " + b ; int n = s . Length ; int [ ] z = new int [ n ] ; compute_z ( s , z ) ; for ( int i = 1 ; i <= n - 1 ; i ++ ) { if ( z [ i ] == a . Length ) { ans ++ ; } } return ans ; } public static void Main ( string [ ] args ) { string a = "101" ; string b = "101" ; Console . WriteLine ( countPermutation ( a , b ) ) ; } }