暴力匹配算法
对主串及模式串进行遍历，如果匹配失败，则主串取下一位置，模式串取起始位置，继续进行遍历。
思路：
暴力匹配算法思路
代码实现：
#include<stdio.h>
int index(char S[], int sLen, char T[], int tLen) { //暴力匹配算法，返回匹配结果的起始位置索引
int i = 0;
int j = 0;
while(i < sLen && j < tLen) {
if(S[i] == T[j]) { //如果主串元素跟模式串元素相同
i++;
j++;
} else { //如果主串元素跟模式串元素不同
i = i - j + 1;
j = 0;
}
}
if(j == tLen) {
return i - tLen;
}
return 0;
}
void main() {
char S[] = "abaeabcdabaebabdeabadabaeabcdabab";
int sLen = 33;
char T[] = "abab";
int tLen = 4;
int result = index(S, sLen, T, tLen);
printf("result: %d \n", result);
}
KMP算法
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。匹配失败后的信息指的是模式串的子串前缀、后缀公共元素最大长度。
思路：
KMP算法思路
代码实现：
#include<stdio.h>
#define MAX 100
/*
1.关于前缀、后缀：
a ==> 无前缀、无后缀
abc ==> 前缀：a ab、后缀：c bc
2.确定前缀、后缀公共元素最大长度：
0 1 2 3 4 5 6 7 ==> 索引
a b c d a b c a ==> 模式串
j i ==> 模式串起始位置到i组成一个子串，j用于记录该子串前缀、后缀公共元素最大长度（j+1）
0 0 0 0 1 2 3 ? ==> 模式串起始位置到i组成的子串的前缀、后缀公共元素最大长度，该例子最终值为：0 0 0 0 1 2 3 1
*/
void get_next(char T[], int tLen, int next[]) { //确定模式串子串的前缀、后缀公共元素最大长度
int j = 0;
int i = 1;
next[0] = 0; //模式串起始位置无前缀、后缀，因此前缀、后缀公共元素最大长度为0
while(i < tLen) { //遍历模式串
if(T[i] == T[j]) { //子串结尾位置元素与j记录位置元素相同时
next[i] = j + 1; //起始位置到i组成的子串的前缀、后缀公共元素最大长度为j+1
++i;
++j;
} else { //子串结尾位置元素与j记录位置元素不相同时
if(j != 0) { //如果j不为0，则取起始位置到j-1组成的子串的前缀、后缀公共元素最大长度，进行下一次比较
j = next[j-1];
} else { //如果j为0，则起始位置到i组成的子串的前缀、后缀公共元素最大长度为0
next[i] = 0;
++i;
}
}
}
}
int KMP(char S[], int sLen, char T[], int tLen) { //KMP算法，返回匹配结果的起始位置索引
int next[MAX]; //存放前缀、后缀公共元素最大长度
get_next(T, tLen, next);
int i = 0;
int j = 0;
while(j<tLen && i<sLen) { //遍历主串与模式串
if(T[j] == S[i]) { //主串与模式串元素相同
++i;
++j;
} else { //主串与模式串元素不同
if(j != 0) { //如果j不为0，则取起始位置到j-1组成的子串的前缀、后缀公共元素最大长度，进行下一次比较
j = next[j-1];
} else { //如果j为0，则对i递增，进行下一次比较
++i;
}
}
}
if(j == tLen) { //循环结束，如果j等于模式串长度，则匹配到结果
return i - tLen;
}
return -1;
}
void main() {
char S[] = "abaeabcdabaebabdeabadabaeabcdabab";
int sLen = 33;
char T[] = "abab";
int tLen = 4;
int next[MAX];
get_next(T, tLen, next);
for(int i=0; i<tLen; i++) {
printf("%d ", next[i]);
}
printf("\n");
int index = KMP(S, sLen, T, tLen);
printf("result: %d \n", index);
}
BM算法
BM算法针对两个子串的比较是从后向前进行的，也就是按照下标从大到小进行比较。BM算法包含两部分，分别是坏字符规则和好后缀规则。
BM算法规则
思路：
BM算法思路
代码实现：
#include<stdio.h>
#define HASH_SIZE 256
#define MAX 100
// 生成坏字符对应的散列表
void create_bad_char(char T[], int tLen, int bad_char[]) {
// 所有坏字符对应的值默认为 -1
for(int i=0; i<HASH_SIZE; i++) {
bad_char[i] = -1;
}
for(int i=0; i<tLen; i++) { //遍历模式串
int ascii = T[i] - '\0'; // 坏字符对应的 ASCII 码，作为下标
bad_char[ascii] = i; // 坏字符在模式串中出现的位置，作为值
}
}
// 求公共后缀子串
// suffix[i]：下标表示后缀子串的长度，值表示与这个后缀子串匹配的另一个子串在模式串中的起始位置
// prefix[i]：下标表示后缀子串的长度，值表示模式串的后缀子串是否能匹配其前缀子串
void create_good_suffix(char T[], int tLen, int suffix[], bool prefix[]) {
for(int i=0; i<tLen; i++) {
suffix[i] = -1;
prefix[i] = false;
}
// 求[0, i]的子串和模式串的公共后缀子串
for (int i=0; i<tLen-1; i++) { //从0遍历到tLen-2
int j = i; //i表示分界，j表示从分界往前求
int k = 0; //k表示公共后缀子串的长度，从0开始求起
while(j>=0 && T[j] == T[tLen-1-k]) { // 下标都向前移动
j--;
k++;
}
if (k != 0) {
suffix[k] = j + 1; // 公共后缀长度为k，起始位置为j+1
}
if (j == -1) {
prefix[k] = true; // 公共后缀子串同时也是模式串的前缀子串
}
}
}
// 根据好后缀规则求下一次移动的位数
int move_by_good_suffix(int j, int tLen, int suffix[], bool prefix[]) { //j为主串坏字符对齐模式串中的位置
int k = tLen - 1 - j; // 好后缀长度
printf("好后缀长度：%d\n", k);
//注意：对于公共后缀长度等于好后缀长度的情况，需要用到公共后缀起始位置来计算下一次移动的位数
if (suffix[k] != -1) { //长度为k的公共后缀存在，suffix[k]表示公共后缀起始位置
printf("找到好后缀，返回移动位数：%d\n", j - suffix[k] + 1);
return j - suffix[k] + 1;
}
//长度为k的公共后缀不存在
for (int r=j+2; r<tLen; r++) {
printf("好后缀子串长度：%d，是否模式串前缀：%d\n", tLen-r, prefix[tLen-r]);
//注意：对于公共后缀长度等于好后缀子串长度的情况，不需要用到公共后缀起始位置来计算下一次移动的位数，而是需要知道是否有公共后缀处于模式串起始位置，因此即使存在多个公共后缀也不影响后续计算
//例如主串：fmewsedkedsed、模式串：ededsed，有两个公共后缀ed，在好后缀规则计算时，后面的ed位置会覆盖前面的ed位置，这个没有关系，我们只要标记好有ed处于模式串起始位置即可
if (prefix[tLen-r] == true) { //tLen-r：tLen-1-r+1,即从r到tLen-1的长度。这里判断长度为tLen-r的公共后缀是否存在并且该公共后缀是否为模式串的前缀子串
printf("找到模式串前缀，返回移动位数：%d\n", r);
return r; //移动位数为r
}
}
printf("返回默认移动位数：%d\n", tLen);
return tLen; //移动位数为tLen
}
int BM(char S[], int sLen, char T[], int tLen) {
int bad_char[HASH_SIZE]; // 记录每个字符在模式串中最后出现的位置，作为坏字符散列表
create_bad_char(T, tLen, bad_char); //坏字符
int suffix[MAX];
bool prefix[MAX];
create_good_suffix(T, tLen, suffix, prefix); //好后缀
for(int m=0; m<tLen; m++) {
printf("suffix[%d]: %d, prefix[%d]: %d\n", m, suffix[m], m, prefix[m]);
}
int i = 0; // 表示主串和模式串对齐时第一个字符的位置
int si = 0; // 坏字符对齐于模式串中的位置
int xi = -1; // 坏字符在模式串中最后出现的位置
while (i <= sLen-tLen) {
int j = 0; //表示主串坏字符对齐模式串中的位置
// 从后向前进行匹配
for (j=tLen-1; j >= 0; j--) {
// 找到了第一个不匹配的字符
if (S[i+j] != T[j]) {
break;
}
}
if (j < 0) { // 匹配成功
return i;
}
si = j;
xi = bad_char[S[i+j] - '\0'];
int x = si - xi; // 坏字符规则应该向后移动的位数
printf("坏字符: si:%d - xi:%d = x:%d\n", si, xi, x);
int y = 0; // 好后缀规则应该向后移动的位数
if (j < tLen-1) {
y = move_by_good_suffix(j, tLen, suffix, prefix);
}
printf("好后缀: %d\n", y);
x = x > y ? x : y; //两个规则取大值
i = i + x; //主串和模式串对齐位置加x
printf("i: %d\n", i);
}
return -1;
}
void main() {
char S[] = "fmewsedkedsed";
int sLen = 13;
char T[] = "ededsed";
int tLen = 7;
//char S[] = "abdeabcdabaeabddeabadabaeabcdaababdbab";
//int sLen = 38;
//char T[] = "ababd";
//int tLen = 5;
int result = BM(S, sLen, T, tLen);
printf("result: %d\n", result);
}
Sunday算法
Sunday算法是对BM算法的小幅优化，与BM算法不同的是，Sunday算法是从前往后匹配，在匹配失败时关注主串中参加匹配的最末位字符的下一位字符。如果该字符没有在模式串中出现则移动位数为：模式串长度+1；否则移动位数为：模式串长度-该字符最右出现的位置(以0开始)，即模式串中该字符最右出现的位置到尾部的距离+1。
思路：
Sunday算法思路
代码实现：
#include<stdio.h>
#define HASH_SIZE 256
int Sunday(char S[], int sLen, char T[], int tLen) {
int move[HASH_SIZE];
//所有字符默认移动位数为tLen+1
for(int i= 0; i<HASH_SIZE; i++) {
move[i] = tLen+1;
}
for (int i = 0; i<tLen; i++) { //遍历模式串,计算当模式串与主串不匹配时，模式串移动位数
move[T[i] - '\0'] = tLen - i;
}
int i = 0; //表示主串和模式串对齐时第一个字符的位置
int j; //表示模式串已经匹配的位置
while(i <= sLen-tLen) {
j = 0;
while(S[i+j] == T[j]) {
j++;
if (j >= tLen){
return i;
}
}
char next = S[i+tLen];
i += move[next];
}
return -1;
}
void main() {
char S[] = "abdeabcdabaeabddeabadabaeabcdaababdbab";
int sLen = 38;
char T[] = "ababd";
int tLen = 5;
int result = Sunday(S, sLen, T, tLen);
printf("result: %d\n", result);
}
网友评论