Рубрики

PHP программа для наивного алгоритма поиска по шаблону

Учитывая текст 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

Поиск по шаблону является важной проблемой в информатике. Когда мы ищем строку в файле блокнота / слова, в браузере или в базе данных, для отображения результатов поиска используются алгоритмы поиска по шаблону.

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

Выход:

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

Пожалуйста, обратитесь к полной статье о наивном алгоритме поиска по шаблону для более подробной информации!

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

PHP программа для наивного алгоритма поиска по шаблону

0.00 (0%) 0 votes