資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法學用 C 編寫的 Rabin-Karp 演算法模式搜尋程式
在該問題中，我們給定兩個字串文字和模式。我們的任務是建立一個用於模式搜尋的 Rabin-Karp 演算法程式，它將找到文字字串中模式的所有出現。
在此，我們必須找到文字中模式的所有出現。
我們舉個例子來理解這個問題：
輸入
text = “xyztrwqxyzfg” pattern = “xyz”
輸出
Found at index 0 Found at index 7
在此，我們將使用 Rabin-Karp 演算法討論該問題的解決方案。在此演算法中，我們在字串中取一個模式大小的視窗，逐個滑動，並將它與模式的雜湊值相匹配。如果雜湊值相符，那麼我們將檢查模式各個字元是否與字串相符。
對於 Rabin-Karp 演算法，文字和模式的雜湊值很重要，對於模式的建立，我們將為
字串的每個字元新增一個字元的數值，並且雜湊值將透過除以一個素數來進行考慮，從而使值較小。
用於模式搜尋的 Rabin-Karp 演算法程式
// 拉賓-卡普演算法用於模式匹配的程式
示例
#include <stdio.h>
#include <string.h>
#define c 256
void search(char pattern[], char text[]){
int M = strlen(pattern);
int N = strlen(text);
int i, j;
int hashP = 0;
int hashT = 0;
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * c) % 103;
for (i = 0; i < M; i++) {
hashP = (c * hashP + pattern[i]) % 103;
hashT = (c * hashT + text[i]) % 103;
}
for (i = 0; i <= N - M; i++) {
if (hashP == hashT) {
for (j = 0; j < M; j++) {
if (text[i + j] != pattern[j])
break;
}
if (j == M)
printf("Pattern found at index %d
", i);
}
if (i < N - M) {
hashT = (c * (hashT - text[i] * h) + text[i + M]) % 103;
if (hashT < 0)
hashT = (hashT + 103);
}
}
}
int main(){
char text[] = "xyztrwqxyzfg";
char pattern[] = "xyz";
printf("The pattern is found in the text at the following index :
");
search(pattern, text);
return 0;
}輸出
在以下索引處找到文字中的模式 -
Pattern found at index 0 Pattern found at index 7
更新日期：17-Jul-2020
310 次瀏覽
廣告