六种字符串匹配算法详解（含代码演示）

article/2025/9/21 12:57:55

1. Brute-Force算法
2. Rabin-Karp Hash算法
3. Kmp算法
4. Kmp的优化算法
5. Sunday算法
6. Shift-And算法

ps：字符串匹配其实是单模匹配问题

1.Brute-Force 朴素匹配算法（暴力匹配）

时间复杂度：O(n*m)

//返回 文本串s中第一次查找到模式串t的位置
int brute_force(const char *s, const char *t){//扫描文本串的每一位for(int i = 0; s[i]; i++){bool flag = true;//用当前的第i位和模式串向后比较for(int j = 0; t[j]; j++){if(s[i + j] == t[j]) continue;flag = false;break;}if(flag) return i;}return -1;
}

2.Rabin-Karp Hash匹配法

时间复杂度：O(n * m / P)

P最好取质数，则最大可以出现P-1种余数，冲突概率为1 / P。当P ~= m，时间复杂度 ~= O(n)

Hash值计算：
在这里插入图片描述

#include<stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>#define MAX_N 10000
#define DEFAULT_LEN 50
char s[MAX_N + 5], t[MAX_N + 5];#define TEST(func){\char temp_s[MAX_N + 5]; \sprintf(temp_s, "%s(\"%s\", \"%s\") = %3d\n", #func, s, t, func(s, t)); \int n = DEFAULT_LEN - strlen(temp_s); \while(n >= 0) n -= printf(" "); \printf("%s", temp_s); \
}typedef long long LL;int brute_one_match(const char *s, const char *t){printf("brute_one_match_called\n");for(int j = 0; t[j]; j++){if(s[j] == t[j]) continue;return 0;}return 1;
}//返回 文本串s中第一次查找到模式串t的位置
int brute_force(const char *s, const char *t){//扫描文本串的每一位for(int i = 0; s[i]; i++){if(brute_one_match(s + i, t)) return i;}return -1;
}//求a^b % c  快速幂
//把a进行二进制分解
int quick_mod(int a, int b, int c){int ans = 1;while(b){//b & 1 --> 取b二进制位的最后一位if(b & 1) ans = (LL)ans * a % c;b >>= 1; //去掉b二进制表示的最后一位a = (LL)a * a % c;}return ans;
}int hash_match(const char *s, const char *t){//base值也最好取一个质数。base取小质数，P取大质数int len = strlen(t), base= 31, P = 9973; //P = 1e9 + 7;int nbase = quick_mod(base, len, P); //base^len % Pint shash = 0, thash = 0;for(int i = 0; t[i]; i++) thash = (thash * base + t[i]) % P;for(int i = 0; s[i]; i++){shash = (shash * base + s[i]) % P;// + P 再 % P保证减完也是正数if(i >= len) shash  = (shash - (s[i - len] * nbase % P) + P) % P;if(i + 1 < len) continue; //所取的文本串s长度还 < 模式串t长度if(shash != thash) continue;//模式串中Hash值相等再按位比较，Hash值本身存在冲突//Hash值相等也不代表模式串匹配成功//按位比较（冲突的时候）if(brute_one_match(s + i - len + 1, t)) return i - len + 1;}return -1;
}int main(){while(scanf("%s%s", s, t)){//根据输出语句可以看出暴力匹配的次数 > hash匹配TEST(brute_force); TEST(hash_match);}return 0;
}

q1:两个不同的字符串拥有相同的哈希值怎么办？

**ans1：**正常比较即可

q2：算法的时间复杂度？

ans2： O(n * m / P)。合理选择P是hash匹配算法的关键

3.KMP算法

时间复杂度O(n + m)

NFA：不确定性有穷状态自动机

在这里插入图片描述

int *getNext(const char *t, int *len){*len = strlen(t);int *next = (int *) malloc (sizeof(int) * (*len)); // next[i] = j : 以i位置结尾，所匹配到的最长前缀是j这个 位置next[0] = -1; //匹配最长前缀不能包含自己，第一位的最长前缀为-1for(int i = 1, j = -1; t[i]; i++){//i是当前匹配的位置，j是i的前一位能匹配到的最长前缀的位置。所以i与j+1比较while(j != -1 && t[j + 1] != t[i]) j = next[j]; //匹配不成功就往前找if(t[j + 1] == t[i]) ++j; //匹配成功就按照i-1位置最长前缀的数量+1next[i] = j;//更新next数组}return next;
}int kmp(const char *s, const char *t){int len = 0;int *next = getNext(t, &len); //初始化next数组//j代表之前成功匹配过的模式串在第几位for(int i = 0, j = -1; s[i]; i++){ while(j != -1 && t[j + 1] != s[i]) j = next[j]; //NFA(不确定性)if(t[j + 1] == s[i]) ++j;if(t[j + 1] == '\0') { //完全成功匹配了模式串free(next);return i - len + 1;}}free(next);return -1;
}

4.KMP的优化：

DFA：确定性有穷状态自动机
在这里插入图片描述

void free_next(int *next){free(next);return ;
}void free_jump(int **jump, int len){for(int i = 0; i < len; i++) free(jump[i - 1]);free(jump - 1);return ;
}//获取跳转信息的数组
int **getJump(int *next, const char *t, int n){int **jump = (int **) malloc(sizeof(int *) * n);for(int i = 0; i < n; i++) jump[i] = (int *) malloc(sizeof(int) * 26);++jump; //让jump指向next数组1的位置，使它访问-1位置的时候实际上访问的是0，合法的for(int i = 0; i < 26; i++) jump[-1][i] = -1;jump[-1][t[0] - 'a'] = 0; //模式串的第一个字符for(int i = 0, I = n - 1; i < I; i++){for(int j = 0; j < 26; j++) jump[i][j] = jump[next[i]][j];jump[i][t[i + 1] - 'a'] = i + 1;}return jump;
}//Kmp的优化算法
int kmp_opt(const char *s, const char *t){int len = 0;int *next = getNext(t, &len);int **jump = getJump(next, t, len); //j代表之前成功匹配过的模式串在第几位for(int i = 0, j = -1; s[i]; i++){ j = jump[j][s[i] - 'a']; //DFA(确定性)if(j == len - 1){ //已找到字符串free_next(next);free_jump(jump, len);return i - len + 1;}}free_next(next);free_jump(jump, len);return -1;
}

4.Sunday算法

匹配效率比KMP高，只需统计每个字母最后一次出现的位置
在这里插入图片描述

int brute_one_match(const char *s, const char *t){printf("brute_one_match_called\n");for(int j = 0; t[j]; j++){if(s[j] == t[j]) continue;return 0;}return 1;
}int sunday(const char *s, const char *t){int tlen = strlen(t), slen = strlen(s);//计算每一种字符出现在字符串的倒数第几位int jump[128] = {0};//默认每个字符出现在模式串的-1位for(int i = 0; i < 128; i++) jump[i] = tlen + 1;//扫描模式串的每一位。t[i]字母出现在倒数第tlen-i位for(int i = 0; t[i]; i++) jump[t[i]] = tlen - i;for(int i = 0; i + tlen <= slen; ){//按位比较，判断当前匹配能否成功if(brute_one_match(s + i, t)) return i;//暴力匹配不成功，计算黄金对齐点位i += jump[s[i + tlen]];}return -1;
}

5.Shift-and算法

效率也比Kmp高
底层思维也是NFA
在这里插入图片描述

int shift_end(const char *s, const char *t){int code[128] = {0}, n = 0;// |= :按位或赋值。x |= 2：计算按位或值2和变量x中的值，并使用按位或赋值运算符将结果分配回x//扫描模式串的每一位。将t[n]字符的第n位置为1for( ; t[n]; n++) code[t[n]] |= (1 << n);int p = 0;for(int i = 0; s[i]; i++){p = (p << 1 | 1) & code[s[i]];if(p & (1 << (n - 1))) return i - n + 1;//p的第n位为1，匹配成功，返回匹配成功的起始位置}return -1;
}