Рубрики

Наивный алгоритм поиска по шаблону

Учитывая текст txt [0..n-1] и шаблон pat [0..m-1] , напишите функцию поиска (char pat [], char txt []), которая печатает все вхождения pat [] в txt. [] . Вы можете предположить, что n> m .

Примеры:

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 ++ программа для наивного паттерна
// Алгоритм поиска
#include <bits/stdc++.h>

using namespace std;

  

void search(char* pat, char* txt)

{

    int M = strlen(pat);

    int N = strlen(txt);

  

    / * Цикл для скольжения [] по очереди * /

    for (int i = 0; i <= N - M; i++) {

        int j;

  

        / * Для текущего индекса i, проверьте соответствие шаблона * /

        for (j = 0; j < M; j++)

            if (txt[i + j] != pat[j])

                break;

  

        if (j == M) // если pat [0 ... M-1] = txt [i, i + 1, ... i + M-1]

            cout << "Pattern found at index "

                 << i << endl;

    }

}

  
// Код драйвера

int main()

{

    char txt[] = "AABAACAADAABAAABAA";

    char pat[] = "AABA";

    search(pat, txt);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C программа для алгоритма поиска наивного шаблона
#include <stdio.h>
#include <string.h>

  

void search(char* pat, char* txt)

{

    int M = strlen(pat);

    int N = strlen(txt);

  

    / * Цикл для скольжения [] по очереди * /

    for (int i = 0; i <= N - M; i++) {

        int j;

  

        / * Для текущего индекса i, проверьте соответствие шаблона * /

        for (j = 0; j < M; j++)

            if (txt[i + j] != pat[j])

                break;

  

        if (j == M) // если pat [0 ... M-1] = txt [i, i + 1, ... i + M-1]

            printf("Pattern found at index %d \n", i);

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    char txt[] = "AABAACAADAABAAABAA";

    char pat[] = "AABA";

    search(pat, txt);

    return 0;

}

Джава

// Java-программа для поиска наивного шаблона

public class NaiveSearch {

  

    public static void search(String txt, String pat)

    {

        int M = pat.length();

        int N = txt.length();

  

        / * Цикл для скольжения по очереди * /

        for (int i = 0; i <= N - M; i++) {

  

            int j;

  

            / * Для текущего индекса i, проверьте шаблон

              совпадение */

            for (j = 0; j < M; j++)

                if (txt.charAt(i + j) != pat.charAt(j))

                    break;

  

            if (j == M) // если 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);

    }

}
// Этот код предоставлен Harikishore

C #

// C # программа для поиска наивного шаблона

using System;

  

class GFG {

  

    public static void search(String txt, String pat)

    {

        int M = pat.Length;

        int N = txt.Length;

  

        / * Цикл для скольжения по очереди * /

        for (int i = 0; i <= N - M; i++) {

            int j;

  

            / * Для текущего индекса i, проверьте шаблон

            совпадение */

            for (j = 0; j < M; j++)

                if (txt[i + j] != pat[j])

                    break;

  

            // если pat [0 ... M-1] = txt [i, i + 1, ... i + M-1]

            if (j == M)

                Console.WriteLine("Pattern found at index " + i);

        }

    }

  

    // Код драйвера

    public static void Main()

    {

        String txt = "AABAACAADAABAAABAA";

        String pat = "AABA";

        search(txt, pat);

    }

}
// Этот код предоставлен Sam007

PHP

<?php
// PHP-программа для Naive Pattern
// Алгоритм поиска

  

function search($pat, $txt)

{

    $M = strlen($pat);

    $N = strlen($txt);

  

    // Цикл для скольжения pat []

    // по одному

    for ($i = 0; $i <= $N - $M; $i++)

    {

  

        // Для текущего индекса i,

        // проверка на соответствие шаблону

        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";

    }

}

  

    // Код драйвера

    $txt = "AABAACAADAABAAABAA";

    $pat = "AABA";

    search($pat, $txt);

      
// Этот код предоставлен Sam007
?>

python3

# Python3 программа для Naive Pattern
# Алгоритм поиска

def search(pat, txt):

    M = len(pat)

    N = len(txt)

  

    # Цикл для скольжения [] по очереди * /

    for i in range(N - M + 1):

        j = 0

          

        # Для текущего индекса я, проверьте

        # для сопоставления с шаблоном * /

        while(j < M):

            if (txt[i + j] != pat[j]):

                break

            j += 1

  

        if (j == M): 

            print("Pattern found at index ", i)

  
Код водителя

if __name__ == '__main__':

    txt = "AABAACAADAABAAABAA"

    pat = "AABA"

    search(pat, txt)

  
# Этот код добавлен
# 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 в следующем посте. Также мы будем писать больше постов, чтобы охватить все алгоритмы поиска по шаблонам и структуры данных.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Наивный алгоритм поиска по шаблону

0.00 (0%) 0 votes