字符串匹配
有一个主串S = {a,b,c,a,c,a,b,d,c},模式串T = {a,b,d},找出模式串在主串中第一次出现的位置。
BF算法既称暴风算法，是普通的模式匹配算法。
对模式串与主串进行比较，从第一个开始比较，符合条件则继续比较主串和模式串的下一个字符，不符合条件则将主串的下一个元素与模式串的第一个比较，以此类推。这个方法的特点是简单、暴力。
这个算法的思路很简单，只需要不断的遍历判断是否相等，即可解决这一类问题
但是他的实行效率并不高，需要进行很多次的遍历去找匹配的字符串
- BF算法-爆发匹配算法
思路: - 分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j的初值为1;
- 如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作:
- S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
- 若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较;
- 如果j > T.length, 说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回0;
int BF(String S, String T, int p){
//记录主串s中当前位置的下标
int i = p;
//用于记录子串的下标
int j = 1;
//若i小于S的长度并且j小于T的长度时，循环继续
while (i<=S[0] && j<=T[0]) {
//比较两个值是否相等
if(S[i] == T[j]){
i++;
j++;
}else{
//回退指针
i = i-j+2;
j = 1;
}
}
//如果j>T[0],匹配成功
if(j>T[0]){
return i-T[0];
}else{
return -1;
}
}
打印结果
15874404406904.png
RK算法
RK算法的核心思想就是将主串或模式串拆分后子串换成一个哈希值
hash：一般我们可以称为“散列”；也可以直接说“哈希”，散列在开发中是常用的手段，例如md5算法就是哈希算法，在安全方面的应用是非常多的，一般一线在1、文件校验，2、数字签名，3、鉴权协议
在我们使用RK算法去解决问题时，我们首先应该想到的是如何将主串分成与子串相同大小的散列值；
例如：
只由数字组成的字符串，这个字符串是由{1，2，3，4，5，6，7，8，9，0}等10个数字组成；如果将十进制数模式串345与十进制数主串{657, 572, 296, 964, 645, 459, 593, 345}逐个比较
d = 10
将模式串转换成散列值：A = 310^2+410+5 = 345
主串转换成散列值：St = 610^2+510+7 = 657
然后在主串中寻找对应的散列值（散列冲突在后面字符串匹配时讲解）
那如果将数字转换成字母，我们应该如何去将字符串转化成散列值呢？
通过前面数字的转换，我们可以通过将“‘当前字母’ - 'a' = 数字”
例如 a-a = 0;
b-a = 1;
c-a = 2;
……
z-a = 25;
"cba" = 'c'*26*26 + 'b'*26 + 'a'*1
= 2*26*26+1*26+0*1
= 1378
那么，主串当中有多个散列值，我们可以找出每个散列值的区别和规律
相邻的两个子串s[i]与s[i+1]（i表示子串从主串中的起始位置，子串的长度都为m）。
对应的哈希值计算公式有交集，也就是说我们可以通过s[i]求得s[i+1]的散列值
以数字为例
657, 572, 729, 294, 945, 457, 573, 345
当i = 1时，
s[i] = 510^2+710+2 = 572
s[i+1] = 710^2+210+9 = 729
因此
s[i+1] = 10（572 - 510^2）+9 = 729
主串分割后的哈希值：St[i+1] = （St[i]-d^2s[i]） d +s[i+m]
同样的可以用字母来实现这样的计算方式
St[i+1] = (St[i]-d^2(s[i+1]-'a')d+s[i+m]-'a')
接下来，我们来了解一下哈希冲突问题：
通过计算散列值来找到匹配的模式串，很有可能会出现重复值，虽然说可能出现的重复值几率很小，但只要有出现的可能性，我们就要解决这个问题。
解决哈希冲突：可以设计更复杂的哈希公式，但是往往一个我们觉得这样有些麻烦，因此，可以计算当散列值相同时，再将两个模式串进行比较，若比较相同，则匹配成功，反之匹配失败。
RK算法的核心思想：
1、如果不做哈希冲突二次核查比较，比较的次数是n-m+1次比较，那么时间复杂度是O(n)。
2、但是要想解决冲突，那就要进行二次核查，那么时间复杂度为O(n*m)。
接下来，用代码演示一下如何实现RK算法
//d 表示进制
#define d 26
//4.为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
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;
}
//3.算出最d进制下的最高位
//d^(m-1)位的值;
int getvalue(int m){
int h = 1;
for (int i = 0; i<m-1; i++) {
h = h*d;
}
return h;
}
/*
* 字符串匹配的RK算法
* Author：Rabin & Karp
* 若成功匹配返回主串中的偏移，否则返回-1
*/
int RK(char *s,char *p){
//1. n:主串长度, m:子串长度
int m = (int)strlen(p);
int n = (int)strlen(s);
printf("主串长度为:%d,子串长度为:%d\n",n,m);
//A.模式串的哈希值; St.主串分解子串的哈希值;
unsigned int A = 0;
unsigned int St = 0;
//2.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值]
//循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue
//此时主串:"abcaadddabceeffccdd" 它的[0,2)是ab
//此时模式串:"cc"
//cc = 2 * 26^1 + 2 *26 ^0 = 52+2 = 54;
//ab = 0 * 26^1 + 1 *26^0 = 0+1 = 1;
for (int i = 0; i!=m; i++) {
A = (d*A+(p[i]-'a'));
St = (d*St+(s[i]-'a'));
}
//3. 获取d^m-1值(因为经常要用d^m-1进制值)
int value = getvalue(m);
//4.遍历[0,n-m], 判断模式串HashValue A是否和其他子串的HashValue 一致.
//不一致则继续求得下一个HashValue
//如果一致则进行二次确认判断,2个字符串是否真正相等.反正哈希值冲突导致错误
//注意细节:
//① 在进入循环时,就已经得到子串的哈希值以及主串的[0,m)的哈希值,可以直接进行第一轮比较;
//② 哈希值相等后,再次用字符串进行比较.防止哈希值冲突;
//③ 如果不相等,利用在循环之前已经计算好的st[0] 来计算后面的st[1];
//④ 在对比过程,并不是一次性把所有的主串子串都求解好Hash值. 而是是借助s[i]来求解s[i+1] . 简单说就是一边比较哈希值,一边计算哈希值;
for (int i =0; i<=n-m; i++) {
if(A == St)
if(isMatch(s, i, p, m))
//加1原因,从1开始数
return i+1;
St = ((St - value*(s[i]-'a'))*d+(s[i+m]-'a'));
}
return -1;
}
打印结果：
15874485334493.png
网友评论