Dados dos arreglos A y B , la tarea es encontrar el índice inicial para cada aparición del arreglo B en el arreglo A usando el algoritmo Z.
Ejemplos:
Entrada: A = {1, 2, 3, 2, 3}, B = {2, 3}
Salida: 1 3
Explicación:
En la array A, la array B se encuentra en el índice 1 y el índice 3. Por lo tanto, la respuesta es {1, 3}.
Entrada: A = {1, 1, 1, 1, 1}, B = {1}
Salida: 0 1 2 3 4
En la array A, la array B se encuentra en el índice {0, 1, 2, 3, 4}.
En Z-Algorithm , construimos un Z-Array.
¿Qué es Z-Array?
Para un arr[0..n-1] , el arreglo Z es un arreglo, de la misma longitud que el arreglo de strings arr, donde cada elemento Z[i] del arreglo Z almacena la longitud de la substring más larga a partir de arr[i] que también es un prefijo de arr[0..n-1]. La primera entrada de la array Z no tiene sentido ya que la array completa siempre es un prefijo de sí misma.
Por ejemplo: Para una array dada arr[] = { 1, 2, 3, 0, 1, 2, 3, 5}
Acercarse:
- Combine la array B y la array A con un separador en el medio en una nueva array C. Aquí el separador puede ser cualquier carácter especial.
- Cree una array Z utilizando la array C.
- Iterar sobre el arreglo Z e imprimir todos aquellos índices cuyo valor sea mayor o igual a la longitud del arreglo B.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP implementation for pattern
// searching in an array using Z-Algorithm
#include<bits/stdc++.h>
using namespace std;
// Function to calculate Z-Array
vector<int> zArray(vector<int> arr)
{
int n = arr.size();
vector<int> z(n);
int r = 0, l = 0;
// Loop to calculate Z-Array
for (int k = 1; k < n; k++) {
// Outside the Z-box
if (k > r) {
r = l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
// Inside Z-box
else {
int k1 = k - l;
if (z[k1] < r - k + 1)
z[k] = z[k1];
else {
l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
}
}
return z;
}
// Helper function to merge two
// arrays and create a single array
vector<int> mergeArray(vector<int> A, vector<int> B)
{
int n = A.size();
int m = B.size();
vector<int> z;
// Array to store merged array
vector<int> c(n + m + 1);
// Copying array B
for (int i = 0; i < m; i++)
c[i] = B[i];
// Adding a separator
c[m] = INT_MAX;
// Copying array A
for (int i = 0; i < n; i++)
c[m + i + 1] = A[i];
// Calling Z-function
z = zArray(c);
return z;
}
// Function to help compute the Z array
void findZArray(vector<int>A,vector<int>B, int n)
{
int flag = 0;
vector<int> z;
z = mergeArray(A, B);
// Printing indexes where array B occur
for (int i = 0; i < z.size(); i++) {
if (z[i] == n) {
cout << (i - n - 1) << " ";
flag = 1;
}
}
if (flag == 0) {
cout << ("Not Found");
}
}
// Driver Code
int main()
{
vector<int>A{ 1, 2, 3, 2, 3, 2 };
vector<int>B{ 2, 3 };
int n = B.size();
findZArray(A, B, n);
}
// This code is contributed by Surendra_Gangwar
Java
// Java implementation for pattern
// searching in an array using Z-Algorithm
import java.io.*;
import java.util.*;
class GfG {
// Function to calculate Z-Array
private static int[] zArray(int arr[])
{
int z[];
int n = arr.length;
z = new int[n];
int r = 0, l = 0;
// Loop to calculate Z-Array
for (int k = 1; k < n; k++) {
// Outside the Z-box
if (k > r) {
r = l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
// Inside Z-box
else {
int k1 = k - l;
if (z[k1] < r - k + 1)
z[k] = z[k1];
else {
l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
}
}
return z;
}
// Helper function to merge two
// arrays and create a single array
private static int[] mergeArray(int A[],
int B[])
{
int n = A.length;
int m = B.length;
int z[];
// Array to store merged array
int c[] = new int[n + m + 1];
// Copying array B
for (int i = 0; i < m; i++)
c[i] = B[i];
// Adding a separator
c[m] = Integer.MAX_VALUE;
// Copying array A
for (int i = 0; i < n; i++)
c[m + i + 1] = A[i];
// Calling Z-function
z = zArray(c);
return z;
}
// Function to help compute the Z array
private static void findZArray(int A[], int B[], int n)
{
int flag = 0;
int z[];
z = mergeArray(A, B);
// Printing indexes where array B occur
for (int i = 0; i < z.length; i++) {
if (z[i] == n) {
System.out.print((i - n - 1)
+ " ");
flag = 1;
}
}
if (flag == 0) {
System.out.println("Not Found");
}
}
// Driver Code
public static void main(String args[])
{
int A[] = { 1, 2, 3, 2, 3, 2 };
int B[] = { 2, 3 };
int n = B.length;
findZArray(A, B, n);
}
}
Python3
# Python3 implementation for pattern
# searching in an array using Z-Algorithm
import sys;
# Function to calculate Z-Array
def zArray(arr) :
n = len(arr);
z = [0]*n;
r = 0;
l = 0;
# Loop to calculate Z-Array
for k in range(1, n) :
# Outside the Z-box
if (k > r) :
r = l = k;
while (r < n and arr[r] == arr[r - l]) :
r += 1;
z[k] = r - l;
r -= 1;
# Inside Z-box
else :
k1 = k - l;
if (z[k1] < r - k + 1) :
z[k] = z[k1];
else :
l = k;
while (r < n and arr[r] == arr[r - l]) :
r += 1 ;
z[k] = r - l;
r -= 1;
return z;
# Helper function to merge two
# arrays and create a single array
def mergeArray(A,B) :
n = len(A);
m = len(B);
# Array to store merged array
c = [0]*(n + m + 1);
# Copying array B
for i in range(m) :
c[i] = B[i];
# Adding a separator
c[m] = sys.maxsize;
# Copying array A
for i in range(n) :
c[m + i + 1] = A[i];
# Calling Z-function
z = zArray(c);
return z;
# Function to help compute the Z array
def findZArray( A,B, n) :
flag = 0;
z = mergeArray(A, B);
# Printing indexes where array B occur
for i in range(len(z)) :
if (z[i] == n) :
print(i - n - 1, end= " ");
flag = 1;
if (flag == 0) :
print("Not Found");
# Driver Code
if __name__ == "__main__" :
A = [ 1, 2, 3, 2, 3, 2];
B = [ 2, 3 ];
n = len(B);
findZArray(A, B, n);
# This code is contributed by AnkitRai01
C#
// C# implementation for pattern
// searching in an array using Z-Algorithm
using System;
class GfG
{
// Function to calculate Z-Array
private static int[] zArray(int []arr)
{
int []z;
int n = arr.Length;
z = new int[n];
int r = 0, l = 0;
// Loop to calculate Z-Array
for (int k = 1; k < n; k++)
{
// Outside the Z-box
if (k > r)
{
r = l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
// Inside Z-box
else
{
int k1 = k - l;
if (z[k1] < r - k + 1)
z[k] = z[k1];
else
{
l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
}
}
return z;
}
// Helper function to merge two
// arrays and create a single array
private static int[] mergeArray(int []A,
int []B)
{
int n = A.Length;
int m = B.Length;
int []z;
// Array to store merged array
int []c = new int[n + m + 1];
// Copying array B
for (int i = 0; i < m; i++)
c[i] = B[i];
// Adding a separator
c[m] = int.MaxValue;
// Copying array A
for (int i = 0; i < n; i++)
c[m + i + 1] = A[i];
// Calling Z-function
z = zArray(c);
return z;
}
// Function to help compute the Z array
private static void findZArray(int []A, int []B, int n)
{
int flag = 0;
int []z;
z = mergeArray(A, B);
// Printing indexes where array B occur
for (int i = 0; i < z.Length; i++)
{
if (z[i] == n)
{
Console.Write((i - n - 1)
+ " ");
flag = 1;
}
}
if (flag == 0)
{
Console.WriteLine("Not Found");
}
}
// Driver Code
public static void Main()
{
int []A = { 1, 2, 3, 2, 3, 2 };
int []B = { 2, 3 };
int n = B.Length;
findZArray(A, B, n);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation for pattern
// searching in an array using Z-Algorithm
// Function to calculate Z-Array
function zArray(arr) {
let n = arr.length;
let z = new Array(n);
let r = 0, l = 0;
// Loop to calculate Z-Array
for (let k = 1; k < n; k++) {
// Outside the Z-box
if (k > r) {
r = l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
// Inside Z-box
else {
let k1 = k - l;
if (z[k1] < r - k + 1)
z[k] = z[k1];
else {
l = k;
while (r < n
&& arr[r] == arr[r - l])
r++;
z[k] = r - l;
r--;
}
}
}
return z;
}
// Helper function to merge two
// arrays and create a single array
function mergeArray(A, B) {
let n = A.length;
let m = B.length;
let z = new Array();
// Array to store merged array
let c = new Array(n + m + 1);
// Copying array B
for (let i = 0; i < m; i++)
c[i] = B[i];
// Adding a separator
c[m] = Number.MAX_SAFE_INTEGER;
// Copying array A
for (let i = 0; i < n; i++)
c[m + i + 1] = A[i];
// Calling Z-function
z = zArray(c);
return z;
}
// Function to help compute the Z array
function findZArray(A, B, n) {
let flag = 0;
let z = [];
z = mergeArray(A, B);
// Printing indexes where array B occur
for (let i = 0; i < z.length; i++) {
if (z[i] == n) {
document.write((i - n - 1) + " ");
flag = 1;
}
}
if (flag == 0) {
document.write("Not Found");
}
}
// Driver Code
let A = [1, 2, 3, 2, 3, 2];
let B = [2, 3];
let n = B.length;
findZArray(A, B, n);
// This code is contributed by gfgking
</script>
Producción:
1 3
Complejidad Temporal: O(N + M).
Publicación traducida automáticamente
Artículo escrito por ishan_trivedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA