資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝設計
法律研究模式查詢演算法的 Rabin-Karp 演算法的 C 程式
C 的模式匹配 − 我們必須查詢一個字串是否出現在另一個字串中，例如，字串“演算法”存在於字串“樸素演算法”中。如果找到了，那麼就會顯示它的位置（即它出現的位置）。我們傾向於建立一個接收 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(文字、模式、質數)
輸入 − 主文字和模式。另一個質數用於查詢雜湊位置
輸出 − 模式被找到的位置
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
更新於： 2019 年 12 月 24 日
3K+ 次瀏覽
廣告