有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模式串在主串中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母
BF算法
BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。
算法思想
首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止;若S[1]和T[1]不等,则S向右移动一个字符的位置,再依次进行比较。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],则匹配成功;否则失败。
该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M * N)。
代码实现
int Index(String S, String T, int pos) {
int i = pos;
int j = 1;
while (i <= S[0] && j <= T[0]) {
if (S[i] == T[j]) {
i++;
j++;
} else {
i = i - j + 2;
j = 1;
}
}
if (j > T[0]) {
return i - T[0];
} else {
return -1;
}
return 0;
}
RK算法
RK 算法的全称叫作 Rabin-Karp 算法,是为了纪念它的两个发明者而这样命名的。 这个算法其实就是刚刚 BF 算法的升级版。
在 BF 算法中,每次都要对 m 个字符逐个进行比较,这就大大降低了算法的效率。这时候,我们引入哈希算法,对子串逐个求哈希值,然后与模式串的哈希值进行比较来判断两个子串是否匹配。在不考虑哈希冲突的情况下,数字之间的比较就非常快了。
解题思路
1.首先把字母转换成数字,将字母-'a'的值单纯字母的对应的数字
例如
a - a = 0;
b - a = 1;
c - a = 2;
- 将小写字母字符串转换成数字,利用字母26进制
例如
“cba” ='c'
* 26 ^ 2 +'b'
* 26 ^ 1 +'a'
* 26 ^ 0
“cba” =2
* 26 ^ 2 +1
* 26 ^ 1 +0
* 26 ^ 0
- 主串拆分的子串之间的关系
例如
主串:d b c
e d b
=3
* 26 ^ 2 +1
* 26 ^ 1 +2
* 26 ^ 0
主串: db c e
d b
=1
* 26 ^ 2 +2
* 26 ^ 1 +4
* 26 ^ 0
子串哈希值求解的规律:
相邻的2个子串s[i]与s[i + 1],对应的哈希值计算公式有交集,也就是说我们可以使用s[i - 1] 计算出s[i]的哈希值。
St[i] = (St[i - 1] - d ^ (m - 1) * (s[i] - 'a')) * d + (s[i + m] - 'a')
- 处理哈希冲突
- 设计更复杂的哈希公式
- 如果哈希值相等,重新核实
代码实现
#define d 26
int isMatch(char *S, int i, char *P, int m) {
int is, ip;
for (is = i, ip = 0; is != m && ip != m; is++, ip++) {
if (S[is] != P[ip]) {
return 0;
}
}
return 1;
}
/*
d ^ (m - 1) 位的值
*/
int getMaxValue(int m) {
int j = 1;
for (int i = 0; i < m - 1; i++) {
j = j * d;
}
return j;
}
int Index(char *S, char *P) {
int n = (int)strlen(S);
int m = (int)strlen(P);
unsigned int A = 0;
unsigned int St = 0;
for (int i = 0; i != m; i++) {
A = (d * A + (P[i] - 'a'));
St = (d * St + (S[i] - 'a'));
}
int hValue = getMaxValue(m);
for (int i = 0; i <= n - m; i++) {
if (A == St && isMatch(S, i, P, m)) {
return i + 1;
}
St = (St - hValue * (S[i] - 'a')) * d + (S[i + m] - 'a');
}
return -1;
}
Demo:https://github.com/ShoukaiWang/DataStructuresAndAlgorithms
网友评论