패턴 검색을 위한 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는 또 다른 패턴 검색 알고리즘입니다. 그냥 문자열 일치 보다 효율적으로 패턴을 찾기 위해 Rabin과 Karp가 제안한 알고리즘 방법. 순진한 알고리즘과 마찬가지로 창을 이동하여 패턴을 확인하기도 합니다. 해시를 하나씩 검색하지만 모든 경우에 모든 문자를 확인할 필요는 없습니다. 해시가 일치하면 각 문자를 확인합니다. 이런 식으로 텍스트 하위 시퀀스당 하나의 비교만 있으므로 보다 효율적인 패턴 검색 알고리즘이 됩니다.

전처리 시간 - O(m)

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

Algorithm

rabinkarp_algo(text,pattern,prime)

Input

rabinkarp_algo(text,pattern,prime)

Inputstrong>− 텍스트 및 패턴. 해시 위치에서 다른 소수 찾기

output− 패턴의 위치 찾기

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 &ndash; text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End

Example

라이브 데모

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string </p><p>");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched </p><p>");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number </p><p>");
   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 </p><p>", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

output

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

위 내용은 패턴 검색을 위한 Rabin-Karp 알고리즘의 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!