算法—字符串匹配RK算法

有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T 式串在主串中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母。

RK核心思想：

1：将比较复杂的字母串比较，转化为数字比较，模式串T使用特定的哈希公式转化为数字，主串S切分等大小的小串也转化为数字，然后进行数字对比。
2：遍历对比过程中，一边转为为数字，一边进行比较，匹配到了就直接break，减少后续未遍历的转化。

RK核心思想1

RK算法核心思想问题一：如何将模式串或者主串拆分后的子串换算成一个哈希值？

类比三位数数字的加法拆分，转化为10进制的次方加法运算。
针对主串子串的小写字母，我们可以设计相应的哈希函数，转化为26进制的加法拆分。

657=？+？
将‘当前字母’ - 'a' = 数字 ==> 'b' - 'a' = 1; 'c' - 'a' = 2;
结合26进制的推想可以转化如下：
字母转化为数字
字母串转化示例：
字母串转化示例
以上得到了字母串转化为数字的哈希公式：
假设当前字母为x,子串length=m, d=26(26进制）,sum = 0,

公式为：sum = sum +（x-'a') *d^(m-1); 条件：m>0，m--。

RK算法核心思想问题2：子串哈希值求解规律:

相邻的2个子串 s[i] 与 s[i+1] (i表示子串从主串中的起始位置,子串的长度 都为m). 对应的哈希值计算公式有交集. 也就说我们可以使用s[i-1]计算出s[i] 的哈希值;
以数字为例：

数字间的规律

主串分割后的哈希值:St[i+1] = (st[i] - d2 ✖ s[i] ) ✖ d + s[i+m]；
由此得到字母串间的规律：

字母串间的规律

int RK1(char *S, char *P) {
    
    int m = (int)strlen(P);//字串len
    int n = (int)strlen(S);//主串len
    
    double A = 0;//待转化的子串数字声明
    double 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 = 0*26+2;
//        //第二次 A = 2*26+2;
//        A = (d*A + (P[i] - 'a'));
//
//        //第一次 st = 0*26+0
//        //第二次 st = 0*26+1
//        St = (d*St + (S[i] - 'a'));
//
//    }
    
    // 子串and主串切分的转化为数字
    int tempm = m;
    for (int i = 0; i <m; i++,tempm--) {
           
           A = A + (P[i] - 'a') * pow(d,tempm-1);
           
           St = St + (S[i] - 'a') * pow(d, tempm-1);
    }
    
    double maxH = pow(d, m-1);//d^(m-1)
    for (int i = 0; i <= (n-m); i++) {
        if (A == St) {
            if(isMatch1(S, i, P, m)){//2次判定是否匹配，因为有可能h产生哈希冲突导致A == St
                return i + 1;
            }
        }
        St = (St - (maxH * (S[i] - 'a'))) * d + (S[i+m] - 'a');//套用子串哈希值求解规律
    }
    
    return -1;
}
int main() {
    char *buf="abcababcabx";
    char *ptrn="abcabx";
    printf("主串为%s\n",buf);
    printf("子串为%s\n",ptrn);
    
    int index = RK1(buf, ptrn);
    printf("find index : %d\n",index);
    
    return 1;
}