Рубрики

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

Вопрос: Мы обсудили алгоритм сопоставления наивных строк здесь . Рассмотрим ситуацию, когда все символы шаблона различны. Можем ли мы изменить оригинальный алгоритм наивного сопоставления строк, чтобы он лучше работал для шаблонов такого типа. Если мы можем, то каковы изменения в оригинальном алгоритме?

Решение: В исходном алгоритме сопоставления наивной строки мы всегда сдвигаем шаблон на 1. Когда все символы шаблона различны, мы можем скользить шаблон более чем на 1. Давайте посмотрим, как мы можем это сделать. Когда после совпадения j происходит несоответствие, мы знаем, что первый символ шаблона не будет соответствовать символам j, потому что все символы шаблона различны. Таким образом, мы всегда можем скользить по j, не пропуская допустимых сдвигов. Ниже приведен модифицированный код, оптимизированный для специальных шаблонов.

C ++

/ * C ++ программа для модифицированного поиска по наивному образцу
алгоритм, оптимизированный для случаев, когда все
символы шаблона различны * /
#include <bits/stdc++.h>

using namespace std;

  
/ * Модифицированный Наивный Поиск Петтерна
алгоритм, который оптимизирован для
случаи, когда все символы шаблона различны * /

void search(string pat, string txt) 

    int M = pat.size(); 

    int N = txt.size(); 

    int i = 0; 

  

    while (i <= N - M) 

    

        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; 

            i = i + M; 

        

        else if (j == 0) 

            i = i + 1; 

        else

            i = i + j; // сдвигаем шаблон по j

    

  
/ * Код водителя * /

int main() 

    string txt = "ABCEABCDABCEABCD"

    string pat = "ABCD"

    search(pat, txt); 

    return 0; 

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

С

/ * C программа для модифицированного поиска по наивному образцу

  алгоритм, оптимизированный для случаев, когда все

  символы шаблона различны * /

#include<stdio.h>
#include<string.h>

  
/ * Оптимизированный алгоритм поиска Naive Pettern Search

   для случаев, когда все символы шаблона отличаются * /

void search(char pat[], char txt[])

{

    int M = strlen(pat);

    int N = strlen(txt);

    int i = 0;

  

    while (i <= N - M)

    {

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

           i = i + M;

        }

        else if (j == 0)

           i = i + 1;

        else

           i = i + j; // сдвигаем шаблон по j

    }

}

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

int main()

{

   char txt[] = "ABCEABCDABCEABCD";

   char pat[] = "ABCD";

   search(pat, txt);

   return 0;

}

Джава

/ * Java-программа для модифицированного поиска по наивному образцу
алгоритм, оптимизированный для случаев, когда все
символы шаблона различны * /

  

class GFG

{

      
/ * Модифицированный Наивный Поиск Петтерна
алгоритм, который оптимизирован для
случаи, когда все символы шаблона различны * /

static void search(String pat, String txt) 

    int M = pat.length(); 

    int N = txt.length(); 

    int i = 0

  

    while (i <= N - M) 

    

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

            i = i + M; 

        

        else if (j == 0

            i = i + 1

        else

            i = i + j; // сдвигаем шаблон по j

    

  
/ * Код водителя * /

public static void main (String[] args) 

{

    String txt = "ABCEABCDABCEABCD"

    String pat = "ABCD"

    search(pat, txt); 


}

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

питон

# Программа Python для модифицированного поиска по наивному образцу
# алгоритм, оптимизированный для случаев, когда все
# символы шаблона разные

def search(pat, txt):

    M = len(pat)

    N = len(txt)

    i = 0

  

    while i <= N-M:

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

        for j in xrange(M):

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

                break

            j += 1

  

        if j==M:    # if pat [0 ... M-1] = txt [i, i + 1, ... i + M-1]

            print "Pattern found at index " + str(i)

            i = i + M

        elif j==0:

            i = i + 1

        else:

            i = i+ j    # сдвиньте шаблон по j

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

txt = "ABCEABCDABCEABCD"

pat = "ABCD"

search(pat, txt)

  
# Этот код предоставлен Bhavya Jain

C #

/ * C # программа для модифицированного поиска по наивному образцу
алгоритм, оптимизированный для случаев, когда все
символы шаблона различны * /

  

using System;

  

class GFG

{

      
/ * Модифицированный Наивный Поиск Петтерна
алгоритм, который оптимизирован для
случаи, когда все символы шаблона различны * /

static void search(string pat, string txt) 

    int M = pat.Length; 

    int N = txt.Length; 

    int i = 0; 

  

    while (i <= N - M) 

    

        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]

        

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

            i = i + M; 

        

        else if (j == 0) 

            i = i + 1; 

        else

            i = i + j; // сдвигаем шаблон по j

    

  
/ * Код водителя * /

static void Main() 

    string txt = "ABCEABCDABCEABCD"

    string pat = "ABCD"

    search(pat, txt); 


}

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

PHP

<?php
// PHP программа для модифицированного наивного
// Алгоритм поиска по шаблону, который
// оптимизирован для случаев, когда все
// символы шаблона разные

  
/ * Модифицированный Наивный Поиск Петтерна

   алгоритм, который оптимизирован для

   случаи, когда все персонажи

   картина отличается * /

function search($pat, $txt)

{

    $M = strlen($pat);

    $N = strlen($txt);

    $i = 0;

  

    while ($i <= $N - $M)

    {

        $j;

  

        / * Для текущего индекса 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" );

            $i = $i + $M;

        }

        else if ($j == 0)

            $i = $i + 1;

        else

          

            // сдвигаем шаблон по j

            $i = $i + $j

    }

}

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

$txt = "ABCEABCDABCEABCD";

$pat = "ABCD";

search($pat, $txt);

  
// Этот код предоставлен нитин митталь.
?>


Выход:

Pattern found at index 4
Pattern found at index 12

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

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

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

0.00 (0%) 0 votes