您好,登錄后才能下訂單哦!
在C語言中,有幾種高性能的字符串搜索算法,可以用于在一個較大的文本或字符串中查找子字符串
KMP算法是一種線性時間復雜度的字符串搜索算法。它的優點是避免了在不匹配時重新檢查之前已經匹配的字符。KMP算法的時間復雜度為O(n+m),其中n是文本長度,m是模式串(子字符串)的長度。
void kmp_search(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
int pi[m];
// 構建部分匹配表
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[j] != pattern[i]) {
j = pi[j - 1];
}
if (pattern[j] == pattern[i]) {
j++;
}
pi[i] = j;
}
// 搜索
j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && text[i] != pattern[j]) {
j = pi[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
printf("Pattern found at index %d\n", i - m + 1);
j = pi[j - 1];
}
}
}
Boyer-Moore算法是一種從右到左的字符串搜索算法,它通過構建一個跳過表來跳過不可能的匹配。這使得算法在最壞情況下具有O(n/m)的時間復雜度。
void boyer_moore_search(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
int skip[256];
// 構建跳過表
for (int i = 0; i < 256; i++) {
skip[i] = m;
}
for (int i = 0; i < m - 1; i++) {
skip[(int)pattern[i]] = m - i - 1;
}
// 搜索
int i = m - 1;
while (i < n) {
int j = m - 1;
while (j >= 0 && text[i] == pattern[j]) {
i--;
j--;
}
if (j < 0) {
printf("Pattern found at index %d\n", i + 1);
i += m;
} else {
i += skip[(int)text[i]];
}
}
}
Rabin-Karp算法是一種基于哈希的字符串搜索算法。它通過計算模式串和文本子串的哈希值來比較它們。如果哈希值相等,則進行字符級別的比較。Rabin-Karp算法的平均時間復雜度為O(n+m)。
#include <stdbool.h>
// 哈希函數
unsigned long hash(const char *str, int len) {
unsigned long h = 0;
for (int i = 0; i < len; i++) {
h = (h << 4) + str[i];
}
return h;
}
void rabin_karp_search(const char *text, const char *pattern) {
int n = strlen(text);
int m = strlen(pattern);
unsigned long pattern_hash = hash(pattern, m);
for (int i = 0; i <= n - m; i++) {
unsigned long text_hash = hash(&text[i], m);
if (pattern_hash == text_hash) {
bool match = true;
for (int j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
match = false;
break;
}
}
if (match) {
printf("Pattern found at index %d\n", i);
}
}
}
}
這些算法在實際應用中的性能取決于具體問題和數據集。在選擇合適的算法時,請根據你的需求和數據特點進行權衡。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。