朴素的模式搜索算法详细介绍 _数据结构

本文概述

C ++
C
Java
C#
的PHP
Python3

给定文字txt [0..n-1]和一个模式拍[0..m-1], 写一个函数搜索(char pat [], char txt [])打印所有出现的拍[]in文本文件[]。你可能会认为n> 米.
例子：

Input:txt[] = "THIS IS A TEST TEXT" pat[] = "TEST" Output: Pattern found at index 10Input:txt[] ="AABAACAADAABAABA" pat[] ="AABA" Output: Pattern found at index 0 Pattern found at index 9 Pattern found at index 12

模式搜索是计算机科学中的一个重要问题。当我们在记事本/单词文件或浏览器或数据库中搜索字符串时, 将使用模式搜索算法来显示搜索结果。
简单的模式搜索：
将模式一一滑过文字, 然后检查是否匹配。如果找到匹配项, 则再次滑动1以检查后续匹配项。
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

//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; }

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

//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 algorithmfunction 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 ?>

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 + = 1if (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

输出如下：

Pattern found at index 0 Pattern found at index 9 Pattern found at index 13

最好的情况是什么？
最好的情况是当模式的第一个字符根本不在文本中出现时。

txt[] = "AABCCAADDEE" ; pat[] = "FAA" ;

在最佳情况下, 比较次数为O(n)。
最坏的情况是什么？
朴素模式搜索的最坏情况发生在以下情况下。
【朴素的模式搜索算法详细介绍】1)当文字和模式的所有字符都相同时。

txt[] = "AAAAAAAAAAAAAAAAAA" ; pat[] = "AAAAA" ;

2)当仅最后一个字符不同时, 也会发生最坏情况。

txt[] = "AAAAAAAAAAAAAAAAAB" ; pat[] = "AAAAB" ;

最坏情况下的比较次数为O(m *(n-m + 1))。尽管具有重复字符的字符串不太可能出现在英文文本中, 但是它们很可能出现在其他应用程序中(例如, 在二进制文本中)。 KMP匹配算法将最坏情况改善为O(n)。我们将在下一篇文章中介绍KMP。另外, 我们将写更多的文章来介绍所有模式搜索算法和数据结构。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。