1. 题目
有一个主串S={a,b,c,a,c,a,b,d,c},模式串T={a,b,d}，请找出模式串在主串中第一次出现的位置
提示：不需要考虑字符串大小写问题，字符均为小写字母
2. BF算法
BF算法，又称爆发匹配算法，简单来说，就是将模式串一个一个字符与主串进行对比，直到模式串中所有的字符匹配成功。
解法思路：
1、 分别利用计数指针i和j，指示主串S和模式T中当前正待比较的字符位置,i初值为pos,j的初值为1;
2、 如果2个串均为比较到串尾,即i和j均小于等于S和T的长度时, 则循环执行以下的操作:
- S[i]和T[j]比较,若相等,则i 和 j分别指示串中下一个位置,继续比较后续的字符;
- 若不相等,指针后退重新开始匹配. 从主串的下一个字符串(i = i – j + 2)起再重新和模式第一个字符(j = 1)比较;
3、 如果j > T.length, 说明模式T中的每个字符串依次和主串S找中的一个连续字符序列相等,则匹配成功,返回和模式T中第一个字符的字符在主串S中的序号(i-T.length);否则匹配失败,返回0;
- 辅助部分
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 40 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /* 0号单元存放串的长度 */
// chars 转换为String[]
Status CreateString(String T, char *chars){
int i;
if (strlen(chars) > MAXSIZE) {
return ERROR;
}else{
T[0] = strlen(chars); // 串0位置存放字符长度
for (i = 1; i<=T[0]; i++) {
T[i] = *(chars+i-1);
}
return OK;
}
}
- 核心部分
int Question_BF(String S, String T, int pos){
int i = pos; // 指定主串开始匹配的位置
int j = 1;
// 判断i和j 都小于对应的主串模式串的长度 才能进行匹配
while (i<=S[0] && j<=T[0]) {
// 相等时，i，j自加，进行下一个字符的匹配
if (S[i] == T[j]) {
i++;
j++;
}else{
//不相等时，j的的位置要从头开始进行匹配，i应当退回到当次匹配的首位的下一位
// +1 是因为子串的首位从1开始
// 再 +1 是因为要往后移一位进行匹配
j = 1;
i = i-j+2;
}
}
// 如果最终的j大于模式串的长度，就说明while中模式串对比完了所有的字符，即找到了位置
if (j>T[0]) {
return i-T[0];
}else{
return -1;
}
}
3. RK算法
相对来说，比较字母总是不如比较数字大小来的简单，那么我们是否可以将字符通过什么方式来计算出对应的数字结果呢？
我们的前辈，Rabin和Karp就很有想法的，通过设计一个哈希公式，利用字符串对应的哈希值来进行比较。即我们已知的模式串可以计算出它的哈希值，同时将主串拆分出与模式串相同长度的子串来计算哈希值，比较两个哈希值是否相等。
那么问题来了：如何将一个‘bcd’换算成一个哈希值？
- 通过ASCII表可以直到字母对应的ASCII值，‘a’ = 97。
- 字母一共有26位，我们可以设计一个26进制
bcb = ('b'-'a')*26^2 + ('c'-'a')*26^1 + ('b'-'a')*26^0；
其中的2次方，也可以认为是模式串长度m减1得来的。
上边计算字符串的哈希值的逻辑假如理解的话，那我们可以再来想一个问题：主串拆分出来的，相邻两个子串，对应的哈希值计算公式是否有交集？是否可以通过前一个子串的哈希值，来求得下一个子串呢？
我们再来看看：
假如相邻的两个字符为’bcb’和’cba’，他们的哈希计算分别为
bcb = (‘b’-‘a’)*26^2 + ('c'-'a')*26^1 + ('b'-'a')*26^0；
cba = ('c'-'a')*26^2 + ('b'-'a')*26^1 + (‘a’-‘a’)*26^0;
可以看到，‘bcb‘减去了最高位的‘b’，同时后两位的多乘了一次26，然后再加上下一个字符串的最低位’a’，得到的结果就是‘cba’的哈希值。
最终的公式
St[i] = (St[i-1] - 26^(m-1)*(S[i]-'a')) * 26 + (S[i+m]-'a')
ps:St[i]为主串中当前子串的哈希值，St[i-1]为前一个子串的哈希值，m为模式串的长度
那么，两个字符串的哈希值相等，就表示两个字符串就一定相同吗？
答案是不一定的，所以我们还需要进一步进行验证，哈希值相等时，两个字符串是否真的匹配？
- 辅助部分
//d 表示进制 字母是26个 这里可以用26进制来设计
#define d 26
//为了杜绝哈希冲突. 当前发现模式串和子串的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;
}
//算出在d进制下的最高位
//d^(m-1)位的值;
int getMaxValue(int m){
int h = 1;
for(int i = 0;i < m - 1;i++){
h = (h*d);
}
return h;
}
- 核心部分
int Question_RK(char *S, char *P){
// n:主串长度 m:子串长度
int n = (int)strlen(S);
int m = (int)strlen(P);
// 初始化A为模式串的哈希值 St为主串的哈希值
unsigned int A = 0;
unsigned int St = 0;
//2.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值] //循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue
for (int i = 0; i<m; i++) {
//假设模式串为 bcb
// 循环第一次：A = 26*0 + 1;
// 第二次：A = 26*1 + 2;
// 第三次：A = 26^2 + 2*26 + 1;
A = (d * A + (P[i]-'a'));
St = (d * St + (S[i]-'a'));
}
//3. 获取d^m-1值(因为经常要用d^m-1进制值) int hValue = getMaxValue(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)) {
return i+1;
}
}
St = (St - hValue*(S[i]-'a')) * d + (S[i+m]-'a');
}
return -1;
}