Dadas dos strings, en las que una es un patrón (Pattern) y la otra es una expresión de búsqueda. La expresión de búsqueda contiene ‘#’.
El # funciona de la siguiente manera:
- Un # coincide con uno o más caracteres.
- Un # coincide con todos los caracteres antes de encontrar una coincidencia de patrón. Por ejemplo, si pat = «A#B» y el texto es «ACCBB», entonces # coincidiría solo con «CC» y el patrón se consideraría como no encontrado.
Ejemplos:
Input : str = "ABABABA"
pat = "A#B#A"
Output : yes
Input : str = "ABCCB"
pat = "A#B"
Output : yes
Input : str = "ABCABCCE"
pat = "A#C#"
Output : yes
Input : str = "ABCABCCE"
pat = "A#C"
Output : no
Podemos observar que cada vez que nos encontramos con ‘#’, tenemos que considerar tantos caracteres hasta que el siguiente carácter del patrón no sea igual al carácter actual de la string dada. En primer lugar, verificamos si el carácter actual del patrón es igual a ‘#’-
a) Si no es así, verificamos si el carácter actual de la string y el patrón son iguales o no, si son iguales, luego incrementamos ambos contadores, de lo contrario devuelven falso de Solo aquí. No es necesario realizar más comprobaciones.
b) Si es así, entonces tenemos que encontrar la posición de un carácter en el texto que coincida con el siguiente carácter del patrón.
C++
// C++ program for pattern matching
// where a single special character
// can match one more characters
#include<bits/stdc++.h>
using namespace std;
// Returns true if pat matches with text
int regexMatch(string text, string pat)
{
int lenText = text.length();
int letPat = pat.length();
// i is used as an index in pattern
// and j as an index in text
int i = 0, j = 0;
// Traverse through pattern
while (i < letPat)
{
// If current character of
// pattern is not '#'
if (pat[i] != '#')
{
// If does not match with text
if (pat[i] != text[j])
return false;
// If matches, increment i and j
i++;
j++;
}
// Current character is '#'
else
{
// At least one character
// must match with #
j++;
// Match characters with # until
// a matching character is found.
while (text[j] != pat[i + 1])
j++;
// Matching with # is over,
// move ahead in pattern
i++;
}
}
return (j == lenText);
}
// Driver code
int main()
{
string str = "ABABABA";
string pat = "A#B#A";
if (regexMatch(str, pat))
cout << "yes";
else
cout << "no";
return 0;
}
Java
// Java program for pattern matching
// where a single special character
// can match one more characters
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Returns true if pat
// matches with text.
public static boolean regexMatch
(String text, String pat)
{
int lenText = text.length();
int lenPat = pat.length();
char[] Text = text.toCharArray();
char[] Pat = pat.toCharArray();
// i is used as an index in pattern
// and j as an index in text.
int i = 0, j = 0;
// Traverse through pattern
while (i < lenPat)
{
// If current character of
// pattern is not '#'
if (Pat[i] != '#')
{
// If does not match with text.
if (Pat[i] != Text[j])
return false;
// If matches, increment i and j
i++;
j++;
}
// Current character is '#'
else
{
// At least one character
// must match with #
j++;
// Match characters with # until
// a matching character is found.
while (Text[j] != Pat[i + 1])
j++;
// Matching with # is over,
// move ahead in pattern
i++;
}
}
return (j == lenText);
}
// Driver code
public static void main (String[] args)
{
String str = "ABABABA";
String pat = "A#B#A";
if (regexMatch(str, pat))
System.out.println("yes");
else
System.out.println("no");
}
}
// This code is contributed by Mr. Somesh Awasthi
Python3
# Python3 program for pattern matching
# where a single special character
# can match one more characters
# Returns true if pat matches with
# text
def regexMatch(text, pat):
lenText = len(text)
letPat = len(pat)
# i is used as an index in
# pattern and j as an index
# in text
i = 0
j = 0
# Traverse through pattern
while (i < letPat):
# If current character of
# pattern is not '#'
if (pat[i] != '#'):
# If does not match with
# text
if (pat[i] != text[j]):
return False
# If matches, increment
# i and j
i += 1
j += 1
# Current character is '#'
else:
# At least one character
# must match with #
j += 1
# Match characters with # until
# a matching character is found.
while (text[j] != pat[i + 1]):
j += 1
# Matching with # is over,
# move ahead in pattern
i += 1
return (j == lenText)
# Driver code
if __name__ == "__main__":
st = "ABABABA"
pat = "A#B#A"
if (regexMatch(st, pat)):
print("yes")
else:
print("no")
# This code is contributed by Chitranayal
C#
// C# program for pattern matching
// where a single special character
// can match one more characters
using System;
class GFG
{
// Returns true if pat
// matches with text.
public static bool regexMatch
(String text, String pat)
{
int lenText = text.Length;
int lenPat = pat.Length;
char []Text = text.ToCharArray();
char []Pat = pat.ToCharArray();
// i is used as an index in pattern
// and j as an index in text.
int i = 0, j = 0;
// Traverse through pattern
while (i < lenPat)
{
// If current character
// of pattern is not '#'
if (Pat[i] != '#')
{
// If does not match with text.
if (Pat[i] != Text[j])
return false;
// If matches, increment i and j
i++;
j++;
}
// Current character is '#'
else
{
// At least one character
// must match with #
j++;
// Match characters with # until
// a matching character is found.
while (Text[j] != Pat[i + 1])
j++;
// Matching with # is over,
// move ahead in pattern
i++;
}
}
return (j == lenText);
}
// Driver code
public static void Main ()
{
String str = "ABABABA";
String pat = "A#B#A";
if (regexMatch(str, pat))
Console.Write("yes");
else
Console.Write("no");
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program for pattern matching
// where a single special character
// can match one more characters
// Returns true if pat
// matches with text
function regexMatch($text, $pat)
{
$lenText = strlen($text);
$letPat = strlen($pat);
// i is used as an index in pattern
// and j as an index in text
$i = 0; $j = 0;
// Traverse through pattern
while ($i < $letPat)
{
// If current character of
// pattern is not '#'
if ($pat[$i] != '#')
{
// If does not match with text
if ($pat[$i] != $text[$j])
return false;
// If matches, increment i and j
$i++;
$j++;
}
// Current character is '#'
else
{
// At least one character
// must match with #
$j++;
// Match characters with # until
// a matching character is found.
while ($text[$j] != $pat[$i + 1])
$j++;
// Matching with # is over,
// move ahead in pattern
$i++;
}
}
return ($j == $lenText);
}
// Driver code
$str = "ABABABA";
$pat = "A#B#A";
if (regexMatch($str, $pat))
echo "yes";
else
echo "no";
// This code is contributed by nitin mittal
?>
Javascript
<script>
// Javascript program for pattern matching
// where a single special character
// can match one more characters
// Returns true if pat
// matches with text.
function regexMatch(text,pat)
{
let lenText = text.length;
let lenPat = pat.length;
let Text = text.split("");
let Pat = pat.split("");
let i = 0, j = 0;
// Traverse through pattern
while (i < lenPat)
{
// If current character of
// pattern is not '#'
if (Pat[i] != '#')
{
// If does not match with text.
if (Pat[i] != Text[j])
return false;
// If matches, increment i and j
i++;
j++;
}
// Current character is '#'
else
{
// At least one character
// must match with #
j++;
// Match characters with # until
// a matching character is found.
while (Text[j] != Pat[i + 1])
j++;
// Matching with # is over,
// move ahead in pattern
i++;
}
}
return (j == lenText);
}
// Driver code
let str = "ABABABA";
let pat = "A#B#A";
if (regexMatch(str, pat))
document.write("yes");
else
document.write("no");
// This code is contributed by rag2127
</script>
Producción:
yes
Este artículo es una contribución de Roshni Agarwal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA