C 中的模式匹配– 我们必须查找一个字符串是否存在于另一个字符串中，例如，字符串“algorithm”存在于字符串“naive algorithm”中。如果是找到，然后显示它的位置（即它所在的位置）。我们倾向于创建一个接收 2 个字符数组的函数，如果匹配则返回位置否则返回-1。
Input: txt = "HERE IS A NICE CAP" pattern = "NICE"Output: Pattern found at index 10Input: 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 setfor index i of all character in the pattern, do h := (h*maxChar) mod primefor all character index i of pattern, do patHash := (maxChar*patHash + pattern[i]) mod prime strHash := (maxChar*strHash + text[i]) mod primefor 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 breakif 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 + primeEnd
示例
实时演示
#include#includeint 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 stringtutorialspointisthebestprogrammingwebsiteEnter the pattern to be searchedpEnter a prime number3Pattern found at index 8Pattern found at index 21
以上就是Rabin-Karp算法的C程序用于模式搜索的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445355.html
微信扫一扫 
支付宝扫一扫 
