Подсчет циклических перестановок, имеющих XOR с другой двоичной строкой как 0

Опубликовано: 5 Января, 2022

Учитывая две двоичные строки а также . Позволять быть набором всех циклических перестановок строки . Задача - найти сколько струн в наборе когда XORed с давать в результате.
Примеры:

Input: A = “101”, B = “101” 
Output: 1 
S = {“101”, “011”, “110”} 
Only “101” XOR “101” = 0
Input: A = “111”, B = “111” 
Output: 3 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: объединить с участием так что он содержит все его циклические перестановки в виде подстрок. Теперь проблема сводится к тому, чтобы найти количество вхождений шаблона в строке которое может быть решено с использованием алгоритма Z (для поиска линейного временного шаблона).
Ниже представлена реализация описанного выше подхода:

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 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>
Выход:
 1

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023