朴素的模式搜索算法详细介绍

2021年4月14日14:17:33 发表评论 615 次浏览

本文概述

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 10

Input:  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

//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#

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

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

输出如下：

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。另外, 我们将写更多的文章来介绍所有模式搜索算法和数据结构。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。