Recuento de permutaciones cíclicas que tienen XOR con otra string binaria como 0

Posted on by Rudeus Greyrat

Dadas dos strings binarias  A y  B . Sea  S el conjunto de todas las permutaciones cíclicas de string  B . La tarea es encontrar cuántas strings en el conjunto  S cuando XORed con  A dar  0 como resultado.
Ejemplos: 
 

Entrada: A = “101”, B = “101” 
Salida: 1 
S = {“101”, “011”, “110”} 
Solo “101” X O “101” = 0
Entrada: A = “111”, B = “111” 
Salida: 3 
 

Enfoque: Concatenar  B con  B para que contenga todas sus permutaciones cíclicas como substrings. Ahora el problema se reduce a encontrar el número de ocurrencias del patrón  A en la string  B que se puede resolver usando el algoritmo Z (para la búsqueda de patrones de tiempo lineal).
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find bitwise XOR between binary
// string A and all the cyclic permutations
// of binary string B
#include <bits/stdc++.h>
using namespace std;
 
// Implementation of Z-algorithm
// for linear time pattern searching
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--;
            }
        }
    }
}
 
// Function to get the count of the cyclic
// permutations of b that given 0 when XORed with a
int countPermutation(string a, string b)
{
    // concatenate b with b
    b = b + b;
 
    // new b now contains all the cyclic
    // permutations of old b as it's sub-strings
    b = b.substr(0, b.size() - 1);
 
    // concatenate pattern with text
    int ans = 0;
    string s = a + "$" + b;
    int n = s.length();
 
    // Fill z array used in Z algorithm  
    int z[n];
    compute_z(s, z);
 
    for (int i = 1; i <= n - 1; i++) {
 
        // pattern occurs at index i since
        // z value of i equals pattern length
        if (z[i] == a.length())
            ans++;
    }
    return ans;
}
 
// Driver code
int main()
{
    string a = "101";
    string b = "101";
 
    cout << countPermutation(a, b) << endl;
 
    return 0;
}

Java

// Java program to find bitwise XOR between binary
// string A and all the cyclic permutations
// of binary string B
 
public class GFG{
     
    // Implementation of Z-algorithm
    // for linear time pattern searching
    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.charAt(r - l) == s.charAt(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.charAt(r - l) == s.charAt(r))
                        r++;
                    z[i] = r - l;
                    r--;
                }
            }
        }
    }
     
    // Function to get the count of the cyclic
    // permutations of b that given 0 when XORed with a
    static int countPermutation(String a, String b)
    {
        // concatenate b with b
        b = b + b;
        // new b now contains all the cyclic
        // permutations of old b as it's sub-strings
        b = b.substring(0, b.length() - 1);
     
        // concatenate pattern with text
        int ans = 0;
        String s = a + "$" + b;
        int n = s.length();
     
        // Fill z array used in Z algorithm  
        int z[] = new int[n];
        compute_z(s, z);
     
        for (int i = 1; i <= n - 1; i++) {
     
            // pattern occurs at index i since
            // z value of i equals pattern length
            if (z[i] == a.length())
                ans++;
        }
        return ans;
    }
     
     
    // Driver Code
     public static void main(String []args){
          
               String a = "101";
               String b = "101";
               System.out.println(countPermutation(a, b)) ;
     }
     // This code is contributed by ANKITRAI1
}

Python3

# Python 3 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
def compute_z(s, z):
    l = 0
    r = 0
    n = len(s)
    for i in range(1, n, 1):
        if (i > r):
            l = i
            r = i
            while (r < n and s[r - l] == s[r]):
                r += 1
            z[i] = r - l
            r -= 1
     
        else:
            k = i - l
            if (z[k] < r - i + 1):
                z[i] = z[k]
             
            else:
                l = i
                while (r < n and s[r - l] == s[r]):
                    r += 1
                z[i] = r - l
                r -= 1
     
# Function to get the count of the cyclic
# permutations of b that given 0 when XORed with a
def countPermutation(a, b):
     
    # concatenate b with b
    b = b + b
 
    # new b now contains all the cyclic
    # permutations of old b as it's sub-strings
    b = b[0:len(b) - 1]
 
    # concatenate pattern with text
    ans = 0
    s = a + "$" + b
    n = len(s)
 
    # Fill z array used in Z algorithm
    z = [0 for i in range(n)]
    compute_z(s, z)
 
    for i in range(1, n, 1):
         
        # pattern occurs at index i since
        # z value of i equals pattern length
        if (z[i] == len(a)):
            ans += 1
     
    return ans
 
# Driver code
if __name__ == '__main__':
    a = "101"
    b = "101"
 
    print(countPermutation(a, b))
     
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to find bitwise XOR between
// binary string A and all the cyclic
// permutations of binary string B
using System;
 
class GFG
{
 
// Implementation of Z-algorithm
// for linear time pattern searching
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--;
            }
        }
    }
}
 
// Function to get the count of the
// cyclic permutations of b that
// given 0 when XORed with a
public static int countPermutation(string a,
                                   string b)
{
    // concatenate b with b
    b = b + b;
     
    // new b now contains all the cyclic
    // permutations of old b as it's sub-strings
    b = b.Substring(0, b.Length - 1);
 
    // concatenate pattern with text
    int ans = 0;
    string s = a + "$" + b;
    int n = s.Length;
 
    // Fill z array used in Z algorithm
    int[] z = new int[n];
    compute_z(s, z);
 
    for (int i = 1; i <= n - 1; i++)
    {
 
        // pattern occurs at index i since
        // z value of i equals pattern length
        if (z[i] == a.Length)
        {
            ans++;
        }
    }
    return ans;
}
 
// Driver Code
public static void Main(string[] args)
{
    string a = "101";
    string b = "101";
    Console.WriteLine(countPermutation(a, b));
}
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
      // JavaScript 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 compute_z(s, z) {
        var l = 0,
          r = 0;
        var n = s.length;
        for (var 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 {
            var 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--;
            }
          }
        }
      }
 
      // Function to get the count of the
      // cyclic permutations of b that
      // given 0 when XORed with a
      function countPermutation(a, b) {
        // concatenate b with b
        b = b + b;
 
        // new b now contains all the cyclic
        // permutations of old b as it's sub-strings
        b = b.substring(0, b.length - 1);
 
        // concatenate pattern with text
        var ans = 0;
        var s = a + "$" + b;
        var n = s.length;
 
        // Fill z array used in Z algorithm
        var z = new Array(n).fill(0);
        compute_z(s, z);
 
        for (var i = 1; i <= n - 1; i++) {
          // pattern occurs at index i since
          // z value of i equals pattern length
          if (z[i] === a.length) {
            ans++;
          }
        }
        return ans;
      }
 
      // Driver Code
      var a = "101";
      var b = "101";
      document.write(countPermutation(a, b));
       
</script>
Producción: 

1

 

Complejidad de tiempo: O(|a+b|), donde |a+b| es el tamaño de la string (a+b).

Complejidad espacial : O(|a+b|)

Publicación traducida automáticamente

Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *