Rabin-Karp算法的C程序用于模式搜索

WBOY
WBOY 转载
2023-09-17 09:01:02 210浏览

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)

算法

rabinkarp_algo(text,pattern,prime)

输入

rabinkarp_algo(text,pattern,prime)

输入 strong>− 正文和模式。查找哈希位置的另一个素数

输出− 找到模式的位置

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 

"); scanf ("%s", &txt); printf ("Enter the pattern to be searched

"); scanf ("%s", &pat); int d = 256; printf ("Enter a prime number

"); 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

", 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

以上就是Rabin-Karp算法的C程序用于模式搜索的详细内容,更多请关注php中文网其它相关文章!

声明:本文转载于:tutorialspoint,如有侵犯,请联系admin@php.cn删除