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#include 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中文網其他相關文章！
