Pregunta: Hemos discutido el algoritmo de coincidencia Naive String aquí . Considere una situación en la que todos los caracteres del patrón son diferentes. ¿Podemos modificar el algoritmo Naive String Matching original para que funcione mejor con este tipo de patrones? Si podemos, ¿cuáles son los cambios en el algoritmo original?
Solución: en el algoritmo de coincidencia original de Naive String , siempre deslizamos el patrón en 1. Cuando todos los caracteres del patrón son diferentes, podemos deslizar el patrón en más de 1. Veamos cómo podemos hacer esto. Cuando ocurre una discrepancia después de las coincidencias j, sabemos que el primer carácter del patrón no coincidirá con los j caracteres coincidentes porque todos los caracteres del patrón son diferentes. Entonces siempre podemos deslizar el patrón por j sin perder ningún cambio válido. A continuación se muestra el código modificado que está optimizado para los patrones especiales.
NB: este algoritmo solo funciona cuando el patrón de búsqueda tiene todos los caracteres diferentes.
C++
/* C++ program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
#include <bits/stdc++.h>
using namespace std;
/* A modified Naive Pattern Searching
algorithm that is optimized for the
cases when all characters of pattern are different */
void search(string pat, string txt)
{
int M = pat.size();
int N = txt.size();
int i = 0;
while (i <= N - M) {
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
cout << "Pattern found at index " << i << endl;
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver code*/
int main()
{
string txt = "ABCEABCDABCEABCD";
string pat = "ABCD";
search(pat, txt);
return 0;
}
// This code is contributed by rathbhupendra
C
/* C program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
#include <stdio.h>
#include <string.h>
/* A modified Naive Pattern Searching algorithm that is optimized
for the cases when all characters of pattern are different */
void search(char pat[], char txt[])
{
int M = strlen(pat);
int N = strlen(txt);
int i = 0;
while (i <= N - M) {
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
printf("Pattern found at index %d \n", i);
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver program to test above function */
int main()
{
char txt[] = "ABCEABCDABCEABCD";
char pat[] = "ABCD";
search(pat, txt);
return 0;
}
Java
/* Java program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
class GFG {
/* A modified Naive Pattern Searching
algorithm that is optimized for the
cases when all characters of pattern are different */
static void search(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
int i = 0;
while (i <= N - M) {
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt.charAt(i + j) != pat.charAt(j))
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
System.out.println("Pattern found at index " + i);
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver code*/
public static void main(String[] args)
{
String txt = "ABCEABCDABCEABCD";
String pat = "ABCD";
search(pat, txt);
}
}
// This code is contributed by chandan_jnu
Python3
# Python program for A modified Naive Pattern Searching
# algorithm that is optimized for the cases when all
# characters of pattern are different
def search(pat, txt):
M = len(pat)
N = len(txt)
i = 0
while i <= N-M:
# For current index i, check for pattern match
for j in range(M):
if txt[i + j] != pat[j]:
break
j += 1
if j == M: # if pat[0...M-1] = txt[i, i + 1, ...i + M-1]
print ("Pattern found at index " + str(i))
i = i + M
elif j == 0:
i = i + 1
else:
i = i + j # slide the pattern by j
# Driver program to test the above function
txt = "ABCEABCDABCEABCD"
pat = "ABCD"
search(pat, txt)
# This code is contributed by Bhavya Jain
C#
/* C# program for A modified Naive Pattern Searching
algorithm that is optimized for the cases when all
characters of pattern are different */
using System;
class GFG {
/* A modified Naive Pattern Searching
algorithm that is optimized for the
cases when all characters of pattern are different */
static void search(string pat, string txt)
{
int M = pat.Length;
int N = txt.Length;
int i = 0;
while (i <= N - M) {
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
Console.WriteLine("Pattern found at index " + i);
i = i + M;
}
else if (j == 0)
i = i + 1;
else
i = i + j; // slide the pattern by j
}
}
/* Driver code*/
static void Main()
{
string txt = "ABCEABCDABCEABCD";
string pat = "ABCD";
search(pat, txt);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP program for A modified Naive
// Pattern Searching algorithm that
// is optimized for the cases when all
// characters of pattern are different
/* A modified Naive Pattern Searching
algorithm that is optimized for the
cases when all characters of
pattern are different */
function search($pat, $txt)
{
$M = strlen($pat);
$N = strlen($txt);
$i = 0;
while ($i <= $N - $M)
{
$j;
/* For current index i,
check for pattern match */
for ($j = 0; $j < $M; $j++)
if ($txt[$i + $j] != $pat[$j])
break;
// if pat[0...M-1] =
// txt[i, i+1, ...i+M-1]
if ($j == $M)
{
echo("Pattern found at index $i"."\n" );
$i = $i + $M;
}
else if ($j == 0)
$i = $i + 1;
else
// slide the pattern by j
$i = $i + $j;
}
}
// Driver Code
$txt = "ABCEABCDABCEABCD";
$pat = "ABCD";
search($pat, $txt);
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript program for A modified
// Naive Pattern Searching algorithm
// that is optimized for the cases
// when all characters of pattern
// are different
// A modified Naive Pattern Searching
// algorithm that is optimized for the
// cases when all characters of pattern
// are different
function search(pat, txt)
{
let M = pat.length;
let N = txt.length;
let i = 0;
while (i <= N - M)
{
let j;
// For current index i, check
// for pattern match
for(j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
// If pat[0...M-1] = txt[i, i+1, ...i+M-1]
if (j == M)
{
document.write("Pattern found at index " +
i + "<br/>");
i = i + M;
}
else if (j == 0)
i = i + 1;
else
// Slide the pattern by j
i = i + j;
}
}
// Driver code
let txt = "ABCEABCDABCEABCD";
let pat = "ABCD";
search(pat, txt);
// This code is contributed by target_2
</script>
Producción:
Pattern found at index 4 Pattern found at index 12
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