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

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

## 本文概述

``````Input:  txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: Pattern found at index 10

pat[] =  "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12``````

## 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 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 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 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 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
\$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__' :
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" ;``````

1)当文字和模式的所有字符都相同时。

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

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

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