Рубрики

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

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

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

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

}

Выход:

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

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

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

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

0.00 (0%) 0 votes