Naiver Algorithmus für die Mustersuche
Schreiben Sie bei einem gegebenen Text txt[0..n-1] und einem Muster pat[0..m-1] eine Funktion search(char pat[], char txt[]) , die alle Vorkommen von pat[] in txt ausgibt [] . Sie können davon ausgehen, dass n > m .
Beispiele:
Input: txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: Pattern found at index 10
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
Die Mustersuche ist ein wichtiges Problem in der Informatik. Wenn wir nach einer Zeichenfolge in Notepad/Word-Datei oder Browser oder Datenbank suchen, werden Mustersuchalgorithmen verwendet, um die Suchergebnisse anzuzeigen.
Naive Mustersuche:
Schieben Sie die Muster einzeln über den Text und suchen Sie nach Übereinstimmungen. Wenn eine Übereinstimmung gefunden wird, wird der Wert erneut um 1 verschoben, um nach weiteren Übereinstimmungen zu suchen.
C
// C program for Naive Pattern Searching algorithm
#include <stdio.h>
#include <string.h>
void search(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++) {
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);
}
}
/* Driver program to test above function */
int main()
{
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
search(pat, txt);
return 0;
}
C++
// C++ program for Naive Pattern
// Searching algorithm
#include <bits/stdc++.h>
using namespace std;
void search(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++) {
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;
}
}
// Driver Code
int main()
{
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
search(pat, txt);
return 0;
}
// This code is contributed
// by Akanksha Rai
Java
// Java program for Naive Pattern Searching
public class NaiveSearch {
public static void search(String txt, String pat)
{
int M = pat.length();
int N = txt.length();
/* A loop to slide pat one by one */
for (int i = 0; i <= N - M; i++) {
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);
}
}
public static void main(String[] args)
{
String txt = "AABAACAADAABAAABAA";
String pat = "AABA";
search(txt, pat);
}
}
// This code is contributed by Harikishore
Python3
# Python3 program for Naive Pattern
# Searching algorithm
def search(pat, txt):
M = len(pat)
N = len(txt)
# A loop to slide pat[] one by one */
for i in range(N - M + 1):
j = 0
# For current index i, check
# for pattern match */
while(j < M):
if (txt[i + j] != pat[j]):
break
j += 1
if (j == M):
print("Pattern found at index ", i)
# Driver Code
if __name__ == '__main__':
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
# This code is contributed
# by PrinciRaj1992
C#
// C# program for Naive Pattern Searching
using System;
class GFG {
public static void search(String txt, String pat)
{
int M = pat.Length;
int N = txt.Length;
/* A loop to slide pat one by one */
for (int i = 0; i <= N - M; i++) {
int 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)
Console.WriteLine("Pattern found at index " + i);
}
}
// Driver code
public static void Main()
{
String txt = "AABAACAADAABAAABAA";
String pat = "AABA";
search(txt, pat);
}
}
// This code is Contributed by Sam007
PHP
<?php
// PHP program for Naive Pattern
// Searching algorithm
function search($pat, $txt)
{
$M = strlen($pat);
$N = strlen($txt);
// A loop to slide pat[]
// one by one
for ($i = 0; $i <= $N - $M; $i++)
{
// 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";
}
}
// Driver Code
$txt = "AABAACAADAABAAABAA";
$pat = "AABA";
search($pat, $txt);
// This code is contributed by Sam007
?>
Javascript
<script>
// Javascript program for Naive Pattern Searching
function search(txt, pat)
{
let M = pat.length;
let N = txt.length;
/* A loop to slide pat one by one */
for (let i = 0; i <= N - M; i++) {
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>");
}
}
let txt = "AABAACAADAABAAABAA";
let pat = "AABA";
search(txt, pat);
</script>
Ausgabe:
Pattern found at index 0 Pattern found at index 9 Pattern found at index 13
Was ist der beste Fall?
Der beste Fall tritt auf, wenn das erste Zeichen des Musters überhaupt nicht im Text vorhanden ist.
C
txt[] = "AABCCAADDEE"; pat[] = "FAA";
Die Anzahl der Vergleiche ist im besten Fall O(n).
Was ist der schlimmste Fall?
Der schlimmste Fall der naiven Mustersuche tritt in den folgenden Szenarien auf.
1) Wenn alle Zeichen des Textes und Musters gleich sind.
C
txt[] = "AAAAAAAAAAAAAAAAAA"; pat[] = "AAAAA";
2) Der schlimmste Fall tritt auch auf, wenn nur das letzte Zeichen anders ist.
C
txt[] = "AAAAAAAAAAAAAAAAAB"; pat[] = "AAAAB";
Die Anzahl der Vergleiche beträgt im ungünstigsten Fall O(m*(n-m+1)). Obwohl Zeichenfolgen mit wiederholten Zeichen wahrscheinlich nicht in englischem Text erscheinen, können sie durchaus in anderen Anwendungen vorkommen (z. B. in binären Texten). Der KMP-Matching-Algorithmus verbessert den schlimmsten Fall auf O(n). Wir werden KMP im nächsten Beitrag behandeln. Außerdem werden wir weitere Beiträge schreiben, um alle Mustersuchalgorithmen und Datenstrukturen abzudecken.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .