패턴 검색을 위한 Rabin-Karp 알고리즘을 위한 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

라빈-카프 또 다른 패턴 검색 알고리즘입니다. 보다 효율적인 방법으로 패턴을 찾기 위해 Rabin과 Karp가 제안한 문자열 매칭 알고리즘이다. Naive Algorithm과 마찬가지로 창을 하나씩 이동하여 패턴을 확인하지만 모든 경우에 대해 모든 문자를 확인하지 않고 해시 값을 찾습니다. 해시 값이 일치하면 각 문자에 대해서만 검사를 진행합니다. 이러한 방식으로 텍스트 하위 시퀀스당 하나의 비교만 가능하므로 패턴 검색을 위한 보다 효율적인 알고리즘입니다.

전처리 시간- O(m)

Rabin-Karp 알고리즘의 시간 복잡도는 O(m+n)입니다. 하지만 최악의 경우 O(mn)입니다. .

알고리즘

rabinkarp_algo(텍스트, 패턴, 프라임)

입력 - 본문과 패턴. 해시 위치 찾기의 또 다른 소수

출력 - 패턴이 발견된 위치

Start
   pat_len := pattern Length
   str_len := string Length
   patHash := 0 and strHash := 0, h := 1
   maxChar := total number of characters in character set
for index i of all character in the pattern, do
   h := (h*maxChar) mod prime
for all character index i of pattern, do
   patHash := (maxChar*patHash + pattern[i]) mod prime
   strHash := (maxChar*strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
   if patHash = strHash, then
      for charIndex := 0 to pat_len -1, do
         if text[i+charIndex] ≠ pattern[charIndex], then
         break
if charIndex = pat_len, then
   print the location i as pattern found at i position.
if i < (str_len - pat_len), then
   strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End

예시

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string \n");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched \n");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number \n");
   scanf ("%d", &q);
   int M = strlen (pat);
   int N = strlen (txt);
   int i, j;
   int p = 0;
   int t = 0;
   int h = 1;
   for (i = 0; i < M - 1; i++)
      h = (h * d) % q;
   for (i = 0; i < M; i++){
      p = (d * p + pat[i]) % q;
      t = (d * t + txt[i]) % q;
   }
   for (i = 0; i <= N - M; i++){
      if (p == t){
         for (j = 0; j < M; j++){
            if (txt[i + j] != pat[j])
            break;
         }
         if (j == M)
            printf ("Pattern found at index %d \n", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

출력

Enter the container string
tutorialspointisthebestprogrammingwebsite
Enter the pattern to be searched
p
Enter a prime number
3
Pattern found at index 8
Pattern found at index 21