Dado un entero n y un conjunto de caracteres A de tamaño k , encuentre una string S tal que cada string posible en A de longitud n aparezca exactamente una vez como una substring en S. Tal string se llama secuencia de Bruijn .
Ejemplos:
Entrada: n = 3, k = 2, A = {0, 1)
Salida: 0011101000
Todas las strings posibles de longitud tres (000, 001, 010, 011, 100, 101, 110 y 111) aparecen exactamente una vez como substrings en un.Entrada: n = 2, k = 2, A = {0, 1)
Salida: 01100
Enfoque:
Podemos resolver este problema construyendo un grafo dirigido con k n-1 Nodes con cada Node con k bordes salientes. Cada Node corresponde a una string de tamaño n-1. Cada borde corresponde a uno de los k caracteres en A y agrega ese carácter a la string inicial.
Por ejemplo, si n=3 y k=2, entonces construimos el siguiente gráfico:
- El Node ’01’ está conectado al Node ’11’ a través del borde ‘1’, ya que sumando ‘1’ a ’01’ (y eliminando el primer carácter) obtenemos ’11’.
- Podemos observar que cada Node en este gráfico tiene el mismo grado de entrada y salida, lo que significa que existe un circuito euleriano en este gráfico.
- El circuito euleriano corresponderá a una sucesión de De Bruijn ya que cada combinación de un Node y un borde saliente representa una string única de longitud n.
- La secuencia de De Bruijn contendrá los caracteres del Node inicial y los caracteres de todos los bordes en el orden en que se recorren.
- Por lo tanto, la longitud de la string será k n +n-1. Usaremos el Algoritmo de Hierholzer para encontrar el circuito Euleriano. La complejidad temporal de este enfoque es O(k n ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
unordered_set<string> seen;
vector<int> edges;
// Modified DFS in which no edge
// is traversed twice
void dfs(string node, int& k, string& A)
{
for (int i = 0; i < k; ++i) {
string str = node + A[i];
if (seen.find(str) == seen.end()) {
seen.insert(str);
dfs(str.substr(1), k, A);
edges.push_back(i);
}
}
}
// Function to find a de Bruijn sequence
// of order n on k characters
string deBruijn(int n, int k, string A)
{
// Clearing global variables
seen.clear();
edges.clear();
string startingNode = string(n - 1, A[0]);
dfs(startingNode, k, A);
string S;
// Number of edges
int l = pow(k, n);
for (int i = 0; i < l; ++i)
S += A[edges[i]];
S += startingNode;
return S;
}
// Driver code
int main()
{
int n = 3, k = 2;
string A = "01";
cout << deBruijn(n, k, A);
return 0;
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG
{
static Set<String> seen = new HashSet<String>();
static Vector<Integer> edges = new Vector<Integer>();
// Modified DFS in which no edge
// is traversed twice
static void dfs(String node, int k, String A)
{
for (int i = 0; i < k; ++i)
{
String str = node + A.charAt(i);
if (!seen.contains(str))
{
seen.add(str);
dfs(str.substring(1), k, A);
edges.add(i);
}
}
}
// Function to find a de Bruijn sequence
// of order n on k characters
static String deBruijn(int n, int k, String A)
{
// Clearing global variables
seen.clear();
edges.clear();
String startingNode = string(n - 1, A.charAt(0));
dfs(startingNode, k, A);
String S = "";
// Number of edges
int l = (int) Math.pow(k, n);
for (int i = 0; i < l; ++i)
S += A.charAt(edges.get(i));
S += startingNode;
return S;
}
private static String string(int n, char charAt)
{
String str = "";
for (int i = 0; i < n; i++)
str += charAt;
return str;
}
// Driver code
public static void main(String[] args)
{
int n = 3, k = 2;
String A = "01";
System.out.print(deBruijn(n, k, A));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of # the above approach import math seen = set() edges = [] # Modified DFS in which no edge # is traversed twice def dfs( node, k, A): for i in range(k): str = node + A[i] if (str not in seen): seen.add(str) dfs(str[1:], k, A) edges.append(i) # Function to find a de Bruijn sequence # of order n on k characters def deBruijn(n, k, A): # Clearing global variables seen.clear() edges.clear() startingNode = A[0] * (n - 1) dfs(startingNode, k, A) S = "" # Number of edges l = int(math.pow(k, n)) for i in range(l): S += A[edges[i]] S += startingNode return S # Driver code n = 3 k = 2 A = "01" print(deBruijn(n, k, A)) # This code is contributed by shubhamsingh10
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
static HashSet<String> seen = new HashSet<String>();
static List<int> edges = new List<int>();
// Modified DFS in which no edge
// is traversed twice
static void dfs(String node, int k, String A)
{
for (int i = 0; i < k; ++i)
{
String str = node + A[i];
if (!seen.Contains(str))
{
seen.Add(str);
dfs(str.Substring(1), k, A);
edges.Add(i);
}
}
}
// Function to find a de Bruijn sequence
// of order n on k characters
static String deBruijn(int n, int k, String A)
{
// Clearing global variables
seen.Clear();
edges.Clear();
String startingNode = strings(n - 1, A[0]);
dfs(startingNode, k, A);
String S = "";
// Number of edges
int l = (int) Math.Pow(k, n);
for (int i = 0; i < l; ++i)
S += A[edges[i]];
S += startingNode;
return S;
}
private static String strings(int n, char charAt)
{
String str = "";
for (int i = 0; i < n; i++)
str += charAt;
return str;
}
// Driver code
public static void Main(String[] args)
{
int n = 3, k = 2;
String A = "01";
Console.Write(deBruijn(n, k, A));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of
// the above approach
var seen = new Set();
var edges = [];
// Modified DFS in which no edge
// is traversed twice
function dfs(node, k, A)
{
for (var i = 0; i < k; ++i)
{
var str = node + A[i];
if (!seen.has(str))
{
seen.add(str);
dfs(str.substring(1), k, A);
edges.push(i);
}
}
}
// Function to find a de Bruijn sequence
// of order n on k characters
function deBruijn(n, k, A)
{
// Clearing global variables
seen = new Set();
edges = [];
var startingNode = A[0].repeat(n-1);
dfs(startingNode, k, A);
var S = "";
// Number of edges
var l = Math.pow(k, n);
for (var i = 0; i < l; ++i)
S += A[edges[i]];
S += startingNode;
return S;
}
function strings(n, charAt)
{
var str = "";
for (var i = 0; i < n; i++)
str += charAt;
return str;
}
// Driver code
var n = 3, k = 2;
var A = "01";
document.write(deBruijn(n, k, A));
// This code is contributed by rrrtnx.
</script>
Producción:
0011101000
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA