Dado un texto y un patrón comodín, busque si el patrón comodín coincide con el texto. La coincidencia debe cubrir todo el texto (no texto parcial).
El patrón comodín puede incluir los caracteres ‘?’ y ‘*’:
- ‘?’ – coincide con cualquier carácter individual
- ‘*’: coincide con cualquier secuencia de caracteres (incluida la secuencia vacía)
Prerrequisito: Programación Dinámica | Ejemplos de coincidencia de patrones comodín
:
Text = "baaabab", Pattern = “*****ba*****ab", output : true Pattern = "baaa?ab", output : true Pattern = "ba*a?", output : true Pattern = "a*ab", output : false
Cada ocurrencia de ‘?’ El carácter en el patrón de comodines se puede reemplazar con cualquier otro carácter y cada aparición de ‘*’ con una secuencia de caracteres tal que el patrón de comodines se vuelva idéntico a la string de entrada después del reemplazo.
Hemos discutido una solución aquí que tiene una complejidad de tiempo O (mxn) y espacial O (mxn).
Para aplicar la optimización, primero notaremos el CASO BASE que dice, si la longitud del patrón es cero, la respuesta será verdadera solo si la longitud del texto con el que tenemos que hacer coincidir el patrón también es cero.
Algoritmo:
- Sea i el marcador para señalar el carácter actual del texto.
Sea j el marcador para señalar el carácter actual del patrón.
Deje que index_txt sea el marcador para señalar el carácter de texto en el que encontramos ‘*’ en el patrón.
Deje que index_pat sea el marcador para señalar la posición de ‘*’ en el patrón. - En cualquier instante, si observamos que txt[i] == pat[j], entonces incrementamos tanto i como j ya que no es necesario realizar ninguna operación en este caso.
- Si encontramos pat[j] == ‘?’, entonces se asemeja al caso mencionado en el paso – (2) como ‘?’ tiene la propiedad de coincidir con cualquier carácter individual.
- Si encontramos pat[j] == ‘*’, entonces actualizamos el valor de index_txt e index_pat ya que ‘*’ tiene la propiedad de coincidir con cualquier secuencia de caracteres (incluida la secuencia vacía) e incrementaremos el valor de j a compare el siguiente carácter del patrón con el carácter actual del texto. (Como el carácter representado por i aún no ha sido respondido).
- Ahora, si txt[i] == pat[j], y hemos encontrado un ‘*’ antes, entonces significa que ‘*’ incluía la secuencia vacía, de lo contrario, si txt[i] != pat[j], un carácter debe ser proporcionado por ‘*’ para que tenga lugar la coincidencia de caracteres actual, luego i debe incrementarse como se responde ahora, pero el carácter representado por j aún debe responderse, por lo tanto, j = index_pat + 1, i = index_txt + 1 (ya que ‘*’ también puede capturar otros caracteres), index_txt++ (ya que coincide con el carácter actual en el texto).
- Si el paso – (5) no es válido, eso significa que txt[i] != pat[j], tampoco hemos encontrado un ‘*’ que significa que no es posible que el patrón coincida con la string. (falso retorno).
- Verifique si j alcanzó su valor final o no, luego devuelva la respuesta final.
Veamos el algoritmo anterior en acción, luego pasaremos a la sección de codificación:
texto = “baaabab”
patrón = “*****ba*****ab”
AHORA APLICAMOS EL ALGORITMO
Paso – (1): i = 0 (i –> ‘b’)
j = 0 (j –> ‘*’)
index_txt = -1
index_pat = -1
NOTA: EL BUCLE FUNCIONARÁ HASTA QUE i ALCANCE SU
VALOR FINAL O LA RESPUESTA SE CONVIERTA EN FALSO A LA MITAD.
PRIMERA COMPARACIÓN: –
Como vemos aquí, pat[j] == ‘*’, por lo tanto saltando directamente al paso – (4).
Paso – (4): index_txt = i (index_txt –> ‘b’)
index_pat = j (index_pat –> ‘*’)
j++ (j –> ‘*’)
Después de cuatro comparaciones más: i = 0 (i –> ‘ b’)
j = 5 (j –> ‘b’)
índice_txt = 0 (índice_txt –> ‘b’)
index_pat = 4 (index_pat –> ‘*’)
SEXTA COMPARACIÓN:-
Como vemos aquí que txt[i] == pat[j], pero ya encontramos ‘*’, por lo tanto usando el paso – (5).
Paso – (5) : i = 1 (i –> ‘a’)
j = 6 (j –> ‘a’)
index_txt = 0 (index_txt –> ‘b’)
index_pat = 4 (index_pat –> ‘*’)
SÉPTIMA COMPARACIÓN :-
Paso – (5) : i = 2 (i –> ‘a’)
j = 7 (j –> ‘*’)
index_txt = 0 (index_txt –> ‘b’)
index_pat = 4 (index_pat –> ‘*’)
OCHO COMPARACIÓN :-
Paso – (4) : i = 2 (i –> ‘a’)
j = 8 (j –> ‘*’)
index_txt = 2 (index_txt –> ‘a’)
index_pat = 7 (index_pat –> ‘*’)
Después de cuatro comparaciones más: i = 2 (i –> ‘a’)
j = 12 (j –> ‘a’)
index_txt = 2 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
DECIMOTERCERA COMPARACIÓN :-
Paso – (5) : i = 3 (i –> ‘a’)
j = 13 (j –> ‘b’)
index_txt = 2 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
DECIMOCUARTA COMPARACIÓN :-
Paso – (5) : i = 3 (i –> ‘a’)
j = 12 (j –> ‘a’)
index_txt = 3 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
DECIMOQUINTA COMPARACIÓN :-
Paso – (5) : i = 4 (i –> ‘b’ )
j = 13 (j –> ‘b’)
index_txt = 3 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
DECIMOSEXTA COMPARACIÓN :-
Paso – (5) : i = 5 (i – > ‘a’)
j = 14 (j –> fin)
index_txt = 3 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
DECIMOSÉPTIMA COMPARACIÓN :-
Paso – (5) : i = 4 (i –> ‘b’)
j = 12 (j –> ‘a’)
index_txt = 4 (index_txt –> ‘b’)
index_pat = 11 (index_pat –> ‘*’)
DÉCIMA OCTAVA COMPARACIÓN :-
Paso – (5) : i = 5 (i –> ‘a’)
j = 12 (j –> ‘a’)
index_txt = 5 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
DÉCIMO NOVENA COMPARACIÓN :-
Paso – (5) : i = 6 (i –> ‘b’)
j = 13 (j –> ‘b’ )
index_txt = 5 (index_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
VIGESIMA COMPARACION :-
Paso – (5) : i = 7 (i –> final)
j = 14 (j –> final )
índice_txt = 5 (índice_txt –> ‘a’)
index_pat = 11 (index_pat –> ‘*’)
NOTA: AHORA SALDREMOS DEL BUCLE PARA EJECUTAR EL PASO – 7.
Paso – (7): j ya está presente en su posición final, por lo tanto, la respuesta es verdadera.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement wildcard
// pattern matching algorithm
#include <bits/stdc++.h>
using namespace std;
// Function that matches input text
// with given wildcard pattern
bool strmatch(char txt[], char pat[],
int n, int m)
{
// empty pattern can only
// match with empty string.
// Base Case :
if (m == 0)
return (n == 0);
// step-1 :
// initialize markers :
int i = 0, j = 0, index_txt = -1,
index_pat = -1;
while (i < n)
{
// For step - (2, 5)
if (j < m && txt[i] == pat[j])
{
i++;
j++;
}
// For step - (3)
else if (j < m && pat[j] == '?')
{
i++;
j++;
}
// For step - (4)
else if (j < m && pat[j] == '*')
{
index_txt = i;
index_pat = j;
j++;
}
// For step - (5)
else if (index_pat != -1)
{
j = index_pat + 1;
i = index_txt + 1;
index_txt++;
}
// For step - (6)
else
{
return false;
}
}
// For step - (7)
while (j < m && pat[j] == '*')
{
j++;
}
// Final Check
if (j == m)
{
return true;
}
return false;
}
// Driver code
int main()
{
char str[] = "baaabab";
char pattern[] = "*****ba*****ab";
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
if (strmatch(str, pattern,
strlen(str), strlen(pattern)))
cout << "Yes" << endl;
else
cout << "No" << endl;
char pattern2[] = "a*****ab";
if (strmatch(str, pattern2,
strlen(str), strlen(pattern2)))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
Java
// Java program to implement wildcard
// pattern matching algorithm
class GFG {
// Function that matches input text
// with given wildcard pattern
static boolean strmatch(char txt[], char pat[],
int n, int m)
{
// empty pattern can only
// match with empty string.
// Base Case :
if (m == 0)
return (n == 0);
// step-1 :
// initialize markers :
int i = 0, j = 0, index_txt = -1,
index_pat = -1;
while (i < n)
{
// For step - (2, 5)
if (j < m && txt[i] == pat[j])
{
i++;
j++;
}
// For step - (3)
else if (j < m && pat[j] == '?')
{
i++;
j++;
}
// For step - (4)
else if (j < m && pat[j] == '*')
{
index_txt = i;
index_pat = j;
j++;
}
// For step - (5)
else if (index_pat != -1)
{
j = index_pat + 1;
i = index_txt + 1;
index_txt++;
}
// For step - (6)
else
{
return false;
}
}
// For step - (7)
while (j < m && pat[j] == '*')
{
j++;
}
// Final Check
if (j == m)
{
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
char str[] = "baaabab".toCharArray();
char pattern[] = "*****ba*****ab".toCharArray();
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
if (strmatch(str, pattern, str.length,
pattern.length))
System.out.println("Yes");
else
System.out.println("No");
char pattern2[] = "a*****ab".toCharArray();
if (strmatch(str, pattern2, str.length,
pattern2.length))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement
# wildcard pattern matching
# algorithm
# Function that matches input
# txt with given wildcard pattern
def stringmatch(txt, pat, n, m):
# empty pattern can only
# match with empty sting
# Base case
if (m == 0):
return (n == 0)
# step 1
# initialize markers :
i = 0
j = 0
index_txt = -1
index_pat = -1
while(i < n - 2):
# For step - (2, 5)
if (j < m and txt[i] == pat[j]):
i += 1
j += 1
# For step - (3)
elif(j < m and pat[j] == '?'):
i += 1
j += 1
# For step - (4)
elif(j < m and pat[j] == '*'):
index_txt = i
index_pat = j
j += 1
# For step - (5)
elif(index_pat != -1):
j = index_pat + 1
i = index_txt + 1
index_txt += 1
# For step - (6)
else:
return False
# For step - (7)
while (j < m and pat[j] == '*'):
j += 1
# Final Check
if(j == m):
return True
return False
# Driver code
strr = "baaabab"
pattern = "*****ba*****ab"
# char pattern[] = "ba*****ab"
# char pattern[] = "ba * ab"
# char pattern[] = "a * ab"
if (stringmatch(strr, pattern, len(strr),
len(pattern))):
print("Yes")
else:
print( "No")
pattern2 = "a*****ab";
if (stringmatch(strr, pattern2, len(strr),
len(pattern2))):
print("Yes")
else:
print( "No")
# This code is contributed
# by sahilhelangia
C#
// C# program to implement wildcard
// pattern matching algorithm
using System;
class GFG {
// Function that matches input text
// with given wildcard pattern
static Boolean strmatch(char[] txt, char[] pat,
int n, int m)
{
// empty pattern can only
// match with empty string.
// Base Case :
if (m == 0)
return (n == 0);
// step-1 :
// initialize markers :
int i = 0, j = 0, index_txt = -1,
index_pat = -1;
while (i < n) {
// For step - (2, 5)
if (j < m && txt[i] == pat[j]) {
i++;
j++;
}
// For step - (3)
else if (j < m && pat[j] == '?') {
i++;
j++;
}
// For step - (4)
else if (j < m && pat[j] == '*') {
index_txt = i;
index_pat = j;
j++;
}
// For step - (5)
else if (index_pat != -1) {
j = index_pat + 1;
i = index_txt + 1;
index_txt++;
}
// For step - (6)
else {
return false;
}
}
// For step - (7)
while (j < m && pat[j] == '*') {
j++;
}
// Final Check
if (j == m) {
return true;
}
return false;
}
// Driver code
public static void Main(String[] args)
{
char[] str = "baaabab".ToCharArray();
char[] pattern = "*****ba*****ab".ToCharArray();
// char pattern[] = "ba*****ab";
// char pattern[] = "ba*ab";
// char pattern[] = "a*ab";
if (strmatch(str, pattern, str.Length,
pattern.Length))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
char[] pattern2 = "a*****ab".ToCharArray();
if (strmatch(str, pattern2, str.Length,
pattern2.Length))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to implement wildcard
// pattern matching algorithm
// Function that matches input text
// with given wildcard pattern
function strmatch(txt, pat, n, m)
{
// empty pattern can only
// match with empty string.
// Base Case :
if (m == 0)
return (n == 0);
// step-1 :
// initialize markers :
let i = 0, j = 0, index_txt = -1,
index_pat = -1;
while (i < n) {
// For step - (2, 5)
if (j < m && txt[i] == pat[j]) {
i++;
j++;
}
// For step - (3)
else if (j < m && pat[j] == '?') {
i++;
j++;
}
// For step - (4)
else if (j < m && pat[j] == '*') {
index_txt = i;
index_pat = j;
j++;
}
// For step - (5)
else if (index_pat != -1) {
j = index_pat + 1;
i = index_txt + 1;
index_txt++;
}
// For step - (6)
else {
return false;
}
}
// For step - (7)
while (j < m && pat[j] == '*') {
j++;
}
// Final Check
if (j == m) {
return true;
}
return false;
}
let str = "baaabab".split('');
let pattern = "*****ba*****ab".split('');
if (strmatch(str, pattern, str.length, pattern.length))
document.write("Yes" + "</br>");
else
document.write("No" + "</br>");
let pattern2 = "a*****ab".split('');
if (strmatch(str, pattern2, str.length, pattern2.length))
document.write("Yes" + "</br>");
else
document.write("No");
</script>
Yes No
Análisis de Complejidad:
- Complejidad de tiempo: O(m + n), donde ‘m’ y ‘n’ son las longitudes del texto y el patrón respectivamente.
- Espacio Auxiliar: O(1).
Sin uso de ninguna estructura de datos para almacenar valores.
Publicación traducida automáticamente
Artículo escrito por Shreyash_Pandey_NSIT y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA