Dada una array 2-D array[][] que contiene N arrays, la tarea es encontrar el subarreglo común más largo (LCS) entre N arrays.
Ejemplos:
Entrada : N = 3,
array[][] = { { 0, 1, 2, 3, 4 },
{ 2, 3, 4 },
{ 4, 0, 1, 2, 3 } }
Salida : 2
Explicación : El subcamino común más largo es {2, 3}.Entrada : N = 2,
array[][] = {{0, 1, 2, 3, 4},
{4, 3, 2, 1, 0}}
Salida : 1
Explicación : Los subtrayectos comunes más largos posibles son [0 ], [1], [2], [3] y [4]. Todos tienen una longitud de 1.
Enfoque: Está claro que la longitud de la LCS puede ser de búsqueda binaria . Es decir, si hay un subarreglo común con longitud L , siempre habrá un subarreglo común con una longitud menor que L. Por lo tanto, el marco de búsqueda binaria es el siguiente:
inferior = 0, superior = longitud máxima + 1; // LCS en [inferior, superior).
while (inferior + 1 < superior) {
medio = (inferior + superior) / 2;
if (hay alguna substring común con longitud media) {
inferior = medio;
} más{
superior = medio;
}
}
LCS = inferior;
Entonces, el punto clave aquí es verificar si hay algunos subconjuntos comunes con longitud media. Una forma habitual es adoptar Hashing, es decir, Rabin Karp Hashing .
Hash(S[0..n-1]) = (S[n-1] * MAGIA^0 + S[n-2] * MAGIA^1 + .. + S[n-1-i] * MAGIA^ i + … ) % MOD
El punto más conveniente aquí es que Hash(S[0…i]) puede usarse para calcular Hash(S[l…r]) en tiempo O(1) , con preparación O(N) . Eso es,
Hash(S[l..r]) = (Hash(S[0..r]) – Hash(S[0..l-1]) * MAGIC^(r-l+1)) % MOD
Por lo tanto, se pueden encontrar todos los valores hash de subarreglo con longitud media de dos arreglos dados y luego verificar si hay alguna superposición. Este procedimiento se puede realizar a través de Hash Table en O(|S|) o Set ( Balance Binary Search Tree ) en O(|S|log|S|). Por lo tanto, Binary Search + Hash puede resolver este problema en tiempo O(|S| log|S|). Siga los pasos a continuación para resolver este problema:
- Inicialice la variable min_len con la máxima longitud posible, es decir, INT_MAX .
- Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
- Establezca el valor de min_len como el mínimo de min_len o array[i].size().
- Inicialice las variables que comienzan como 0, terminan como min_len y mid como 0 para realizar la búsqueda binaria en la longitud.
- Atraviese el ciclo while hasta que el inicio sea menor que el final y realice los siguientes pasos:
- Establezca el valor de mid como el promedio de inicio y final.
- Llame a la función check(array, mid) para verificar si la longitud mid es posible como respuesta o no usando el hash de Rabin-karp .
- Si la función devuelve verdadero, establezca el valor de inicio como mid+1; de lo contrario, finalice como mid-1.
- Después de realizar los pasos anteriores, imprima el valor de fin como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const long long p = 1299827;
const long long mod = 1e11 + 7;
long long M;
// Function to implement rabin - carp
// hashing to check whether the given length
// is possible or not
bool check(vector<vector<int> >& array, int len)
{
if (len == 0)
return true;
map<long long, int> freq;
for (int i = 0; i < M; i++) {
long long curr_hash = 0, pow = 1;
set<long long> found_hashes;
for (int j = 0; j < len; j++) {
curr_hash = (curr_hash * p) % mod;
curr_hash += array[i][j];
if (j != len - 1)
pow = (pow * p) % mod;
}
found_hashes.insert(curr_hash);
for (int j = len; j < array[i].size(); j++) {
curr_hash += mod;
curr_hash -= (array[i][j - len] * pow) % mod;
curr_hash %= mod;
curr_hash = curr_hash * p;
curr_hash %= mod;
curr_hash += array[i][j];
curr_hash %= mod;
found_hashes.insert(curr_hash);
}
while (found_hashes.size()) {
long long h = *(found_hashes.begin());
found_hashes.erase(found_hashes.begin());
freq[h]++;
if (freq[h] == M)
return true;
}
}
return false;
}
// Function to find the longest common sub-array
// from the given N arrays
int longestCommonSubpath(long long N,
vector<vector<int> >& array)
{
M = N;
// Find the maximum length possible
int minlen = INT_MAX;
for (int i = 0; i < array.size(); i++) {
minlen = min(minlen, (int)array[i].size());
}
// Binary search on the length
int start = 0, end = minlen, mid = 0;
while (start <= end) {
int mid = (start + end) / 2;
// Function Call to check whether
// it is possible or not
if (check(array, mid)) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return end;
}
// Driver Code
int main()
{
vector<vector<int> > arr{ { 0, 1, 2, 3, 4 },
{ 2, 3, 4 },
{ 4, 0, 1, 2, 3 } };
long long N = arr.size();
cout << longestCommonSubpath(N, arr);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
import java.util.HashSet;
class GFG {
static long p = 1299827;
static long mod = (long) 1E11 + 7;
static long M;
// Function to implement rabin - carp
// hashing to check whether the given length
// is possible or not
static boolean check(int[][] array, int len) {
if (len == 0)
return true;
HashMap<Long, Integer> freq = new HashMap<Long, Integer>();
for (int i = 0; i < M; i++) {
long curr_hash = 0, pow = 1;
HashSet<Long> found_hashes = new HashSet<Long>();
for (int j = 0; j < len; j++) {
curr_hash = (curr_hash * p) % mod;
curr_hash += array[i][j];
if (j != len - 1)
pow = (pow * p) % mod;
}
found_hashes.add(curr_hash);
for (int j = len; j < array[i].length; j++) {
curr_hash += mod;
curr_hash -= (array[i][j - len] * pow) % mod;
curr_hash %= mod;
curr_hash = curr_hash * p;
curr_hash %= mod;
curr_hash += array[i][j];
curr_hash %= mod;
found_hashes.add(curr_hash);
}
while (found_hashes.size() > 0) {
long h = found_hashes.iterator().next();
found_hashes.remove(h);
if (freq.containsKey(h)) {
freq.put(h, freq.get(h) + 1);
} else {
freq.put(h, 1);
}
if (freq.get(h) == M)
return true;
}
}
return false;
}
// Function to find the longest common sub-array
// from the given N arrays
public static int longestCommonSubpath(long N, int[][] array) {
M = N;
// Find the maximum length possible
int minlen = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
minlen = Math.min(minlen, (int) array[i].length);
}
// Binary search on the length
int start = 0, end = minlen, mid = 0;
while (start <= end) {
mid = (start + end) / 2;
// Function Call to check whether
// it is possible or not
if (check(array, mid)) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return end;
}
// Driver Code
public static void main(String args[]) {
int[][] arr = { { 0, 1, 2, 3, 4 }, { 2, 3, 4 }, { 4, 0, 1, 2, 3 } };
long N = arr.length;
System.out.println(longestCommonSubpath(N, arr));
}
}
// This code is contributed by gfgking.
Python3
# Python Program to implement
# the above approach
p = 1299827
mod = 1e11 + 7
M = None
# Function to implement rabin - carp
# hashing to check whether the given length
# is possible or not
def check(array, _len, M):
if (_len == 0):
return True
freq = {}
for i in range(M):
curr_hash = 0
pow = 1
found_hashes = set()
for j in range(_len):
curr_hash = (curr_hash * p) % mod
curr_hash = curr_hash + array[i][j]
if (j != _len - 1):
pow = (pow * p) % mod
found_hashes.add(curr_hash)
for j in range(_len, len(array[i])):
curr_hash = curr_hash + mod
curr_hash = curr_hash - (array[i][j - _len] * pow) % mod
curr_hash = curr_hash % mod
curr_hash = curr_hash * p
curr_hash = curr_hash % mod
curr_hash = curr_hash + array[i][j]
curr_hash = curr_hash % mod
found_hashes.add(curr_hash)
while (len(found_hashes) != 0):
it = list(found_hashes)
# get first entry:
h = it[0]
found_hashes.remove(h)
if (h not in freq):
freq[h] = 1
else:
freq[h] += 1
if (h in freq and freq[h] == M):
return True
return False
# Function to find the longest common sub-array
# from the given N arrays
def longestCommonSubpath(N, array):
M = N
# Find the maximum length possible
minlen = 10 ** 9
for i in range(len(array)):
minlen = min(minlen, len(array[i]))
# Binary search on the length
start = 0
end = minlen
mid = 0
while (start <= end):
mid = (start + end) // 2
# Function Call to check whether
# it is possible or not
if (check(array, mid, M)):
start = mid + 1
else:
end = mid - 1
return end
# Driver Code
arr = [[0, 1, 2, 3, 4], [2, 3, 4], [4, 0, 1, 2, 3]]
N = len(arr)
print(longestCommonSubpath(N, arr))
# This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript Program to implement
// the above approach
let p = 1299827;
let mod = 1e11 + 7;
var M;
// Function to implement rabin - carp
// hashing to check whether the given length
// is possible or not
function check(array, len, M) {
if (len == 0)
return true;
let freq = new Map();
for (let i = 0; i < M; i++) {
let curr_hash = 0, pow = 1;
let found_hashes = new Set();
for (let j = 0; j < len; j++) {
curr_hash = (curr_hash * p) % mod;
curr_hash = curr_hash + array[i][j];
if (j != len - 1)
pow = (pow * p) % mod;
}
found_hashes.add(curr_hash);
for (let j = len; j < array[i].length; j++) {
curr_hash = curr_hash + mod;
curr_hash = curr_hash - (array[i][j - len] * pow) % mod;
curr_hash = curr_hash % mod;
curr_hash = curr_hash * p;
curr_hash = curr_hash % mod;
curr_hash = curr_hash + array[i][j];
curr_hash = curr_hash % mod;
found_hashes.add(curr_hash);
}
while (found_hashes.size != 0)
{
var it = found_hashes.values();
// get first entry:
var first = it.next();
// get value out of the iterator entry:
var h = first.value;
found_hashes.delete(h);
if (freq.has(h) == false) {
freq.set(h, 1)
}
else {
freq.set(h, freq.get(h) + 1)
}
if (freq.has(h) && freq.get(h) == M)
return true;
}
}
return false;
}
// Function to find the longest common sub-array
// from the given N arrays
function longestCommonSubpath(N,
array) {
M = N;
// Find the maximum length possible
let minlen = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < array.length; i++) {
minlen = Math.min(minlen, array[i].length);
}
// Binary search on the length
let start = 0, end = minlen, mid = 0;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
// Function Call to check whether
// it is possible or not
if (check(array, mid, M)) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
return end;
}
// Driver Code
let arr = [[0, 1, 2, 3, 4],
[2, 3, 4],
[4, 0, 1, 2, 3]];
let N = arr.length;
document.write(longestCommonSubpath(N, arr));
// This code is contributed by Potta Lokesh
</script>
2
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sumitsingh32 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA