패턴 검색을 위한 Naive 알고리즘을 위한 C 프로그램

C에서 패턴 일치 − 문자열이 다른 문자열에 존재하는지 확인해야 합니다. 예를 들어 문자열 "algorithm"이 "naive algorithm" 문자열 내에 존재합니다. 발견되면 해당 위치(즉, 존재하는 위치)는 다음과 같습니다. 우리는 2개의 문자 배열을 수신하고 일치가 발생하면 위치를 반환하고 그렇지 않으면 -1을 반환하는 함수를 만드는 경향이 있습니다.

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

우리는 Naive Pattern Searching으로 이 문제를 해결하고 있습니다. 이 알고리즘은 작은 텍스트에 유용합니다. Naive는 한 문자열이 다른 문자열 내에서 발생하는 위치를 확인하는 간단하고 비효율적인 방법은 해당 문자열이 있을 수 있는 모든 위치를 하나씩 검사하여 해당 문자열이 있는지 검사하는 것입니다.

Naive Algorithm의 시간 복잡도는 O(mn)이며, 여기서 m은 검색할 패턴의 크기이고 n은 컨테이너 문자열의 크기입니다.

패턴 검색은 컴퓨터 과학에서 매우 중요한 문제입니다. 메모장/워드 파일, 브라우저, 데이터베이스 또는 일부 정보에서 문자열을 찾을 때마다 패턴 검색 알고리즘을 사용하여 검색 결과를 표시합니다.

알고리즘

naive_algorithm(패턴, 텍스트)

입력 - 텍스트와 패턴

출력 - 텍스트에 패턴이 있는 위치

Start
   pat_len := pattern Size
   str_len := string size
   for i := 0 to (str_len - pat_len), do
      for j := 0 to pat_len, do
         if text[i+j] ≠ pattern[j], then
         break
   if j == patLen, then
   display the position i, as there pattern found
End

예시

#include <stdio.h>
#include <string.h>
int main (){
   char txt[] = "tutorialsPointisthebestplatformforprogrammers";
   char pat[] = "a";
   int M = strlen (pat);
   int N = strlen (txt);
   for (int i = 0; i <= N - M; i++){
      int j;
      for (j = 0; j < M; j++)
         if (txt[i + j] != pat[j])
      break;
      if (j == M)
         printf ("Pattern matches at index %d \n", i);
   }
   return 0;
}

출력

Pattern matches at 6
Pattern matches at 25
Pattern matches at 39