串练习 - 字符串匹配问题

问题

有主串S = "abcacabdc"，模式串T = "abd"，请查找出模式串在主串第一次出现的位置；

提示：主串和模式串均为小写字母且都是合法输入

S = "abcacabdc", T = "abd"
输出： 6

分析

根据题目意思，其实就是判断模式串T是否为主串S的子串

如果是子串，返回子串T的第一个字符在主串S中首次出现位置，否则返回-1

Leetcode上类似题目：实现strStr()

方法一：BF算法

Brute-Force算法是一个纯暴力的算法。

首先，比较2个字符串是否相等，最朴素的思想，就是从前往后逐个字符比较，一旦遇到不相同的字符，就返回false；如果2个字符串都结束了，仍然没有出现不对应的字符，则返回true

枚举 i = 0，1，2...，len(S) - len(T)
将S[i:i+len(T)]与T比较。如果一致，则找到匹配

复杂度

时间复杂度：O(n * m)，一共需要比较m - n次，(m-n + 1) * n，而一般主串比模式串要长，所以复杂度是n*m
空间复杂度：O(1)

/* 写法一 */
int strStr_BF(char * haystack, char * needle){
    
    int m = (int)strlen(haystack);
    int n = (int)strlen(needle);
    
    for (int i = 0; i <= m - n; i++) {
        int flag = TRUE;
        for (int j = 0; needle[j] != '\0'; j++) {
            if (haystack[i + j] != needle[j]) {
                flag = FALSE;
                break;
            }
        }
    
        if (flag) {
            return i;
        }
    }
    return -1;
}


/* 写法二 */
int strStr_BF(char * haystack, char * needle){
    int m = (int)strlen(haystack);
    int n = (int)strlen(needle);
    
    int i = 0;
    int start = 0;
    for (;start < m && i < n;) {
        if (haystack[start] == needle[i]) {
            start++;
            i++;
        }else {
            start = start - i + 1;
            i = 0;
        }
    }
    if (i == n) {
        return start - n;
    }
    return -1;
}

方法二：RK算法

Rabin Karp - 常数复杂度是一种最坏时间复杂度为**O(N)**的算法。

思路：假设我们有某一个hash函数可以将字符串转换为一个整数，则hash结果不同的字符串肯定不同，但hash结果相同的字符串很有可能相同（存在哈希冲突）

分析：主串S = "abcacabdc", 模式串T = "abd"

情况一、$hash(S_{i-m+1}...S_i) == hash(P_0...P_{m-1})$，此时S的子串SV与P有可能匹配成功。只需要逐个字符对比就可以判断是否真的匹配成功。
- 如果匹配成功，则返回匹配成功点的下标i-m+1;
- 若不成功，则继续取S的子串$S_{i-m+2}...S_{i+1}$进行hash比较。
情况二、$hash(S_{i-m+1}...S_i) \neq hash(P_0...P_{m-1})$，此时S的子串SV与P不相等，继续取S的子串$S_{i-m+2}...S_{i+1}$。

综合上面2个情况，可以发现一个共同的操作，就是需要继续取S的子串进行hash比较。如果每次重新求hash值的话，复杂度为O(m)，整体复杂度为O(mn)。如果利用上一个子串的hash结果$hash(S_{i-m+1}...S_i)$，在**O(1)**的时间内求出$S_{i-m+2}...S_{i+1}$，那么可以将整体复杂度降低到线性时间。

现在，问题的关键也就是变成了如何根据$hash(S_{i-m+1}...S_i)$，在**O(1)**的时间内求出$hash(S_{i-m+2}...S_{i+1})$

设计hash函数：

$hash(S_{i-m+1}...S_i) = S_{i-m+1} \times D^{m-1} + S_{i-m+2} \times D^{m-2} + ... + S_i \times D^0$

那么下一个子串的hash值为： $$ hash(S_{i-m+2}...S_{i+1}) = S_{i-m+2} \times D^{m-1} + S_{i-m+3} \times D^{m-2} + ... + S_{i+1} \times D^0 $$

$$ = (hash(S_{i-m+1}...S_{i})- S_{i-m+1} \times D^{m-1}) \times D + S_{i+1} \times D^0 $$

现在还有一个问题，hash结果过大怎么办呢？

大素数取余数，也称为HashSize

所以，hash函数更新为：

$hash(S_{i-m+1}...S_i) = S_{i-m+1} \times D^{m-1} + S_{i-m+2} \times D^{m-2} + ... + S_i \times D^0 \ % \ HashSize$

那么下一个子串的hash值为： $$ hash(S_{i-m+2}...S_{i+1}) = S_{i-m+2} \times D^{m-1} + S_{i-m+3} \times D^{m-2} + ... + S_{i+1} \times D^0 \ % \ HashSize $$

$$ = (hash(S_{i-m+1}...S_{i})- S_{i-m+1} \times D^{m-1}) \times D + S_{i+1} \times D^0 \ % \ HashSize $$

算法原理：

每次从主串S取长度为m的子串，将其hash结果与T的hash结果进行比较
- 若不相同，则继续从主串S中选新的子串进行比较
- 若相同，则有可能匹配成功

算法优化：

用其他运算代替取模运算
降低hash冲突

假设d=10，存在char值为2,20,200的三个字符a,b,c，可以发现a1000，b100，c*10的hash结果是相同的，也就是发生了冲突，所以取大于等于256的数做x则可以避免这种冲突。
另外，HashSize的大小也会决定冲突发生的概率。对于unsigned int来说，总共有$2^{32}$次方个，所以可以取HASHSIZE为$2^{32}$次方。
而计算机对于大于等于$2^{32}$次方的数会自动舍弃高位，其刚好等价于对$2^{32}$次方取模，即对HASHSIZE取模，所以便可以从代码中去掉取模运算。

算法流程：

计算模式串T的hash值以及$D^{m-1}$
循环主串，比较每一个子串的hash值是否与模式串T的hash值相等
- 若hash结果相等，子串S和模式串T逐个字符比较是否相等

复杂度：

时间复杂度：循环复杂度O(n)，hash结果相等时的逐字符匹配复杂度为O(m)，整体时间复杂度为O(m+n)
空间复杂度：O(1)

#define UNSIGNED(x) ((unsigned char) x)
#define D 257 // ascii码

int RK(char *S, char*T) {
    int n = (int)strlen(S);
    int m = (int)strlen(T);
    
    // sv为s子串的hash结果，tv为p的hash结果，base为D的m-1次方
    unsigned int sv = UNSIGNED(S[0]);
    unsigned int tv = UNSIGNED(T[0]);
    unsigned int base = 1;
   
    int i, j;
    for (i = 1; i < m; i++) {
        tv = tv * D + UNSIGNED(T[i]);
        sv = sv * D + UNSIGNED(S[i]);
        base = base * D;
    }
    
    i = m - 1;
    
    do {
      	/* hash值相等 */
        if (!(sv ^ tv)) {
            for (j = 0; j < m && S[i - m + 1 + j] == T[j]; j++) {}
            if (j == m) {
                return i- m+ 1;
            }
        }
        i++;
        if (i >= n) {
            break;
        }
        /* O(1)时间内更新sv
         * sv + UNSIGNED(s[i - m]) * (~base + 1)等价于sv - UNSIGNED(s[i - m]) * base
         */
        sv = (sv + UNSIGNED(S[i - m]) * (~base + 1)) * D + UNSIGNED(S[i]);
    } while (i < n);
 
    return -1;
}

方法三：KMP算法

在分析Brute-Force算法执行过程时，我们可以发现每次当主串与子串比较失败时，需要将子串从头开始比较

最坏的情况下，如上图所示，就需要全部遍历所有的字符。

如果我们需要进行优化，很难降低字符串比较的复杂度（因为字符串比较，真的只能逐个比较字符）。因此，我们考虑降低比较的趟数。

要优化一个算法，首先要回答的问题是“现在手上有什么信息？”我们手上的信息是否足够、是否有效，决定我们能把算法优化到何种程度。

尽可能利用残余的信息，是KMP算法的思想所在。

关于KMP详细的讲解，可以看 KMP 章节

算法流程：

首先根据模式串T求解next数组
借用next数组比较主串S与模式串T

复杂度

时间复杂度：O(n+m)， m是构建next数组的时间复杂度
空间复杂度：O(n)

void buildNext(char *T, int *next) {
    //   abaaba
    //  -100112
    
    int pre = 0; // 前缀
    int suf = 1; // 后缀
    int len = (int)strlen(T);
    next[0] = 0;
    while (suf < len) {
        if (T[suf] == T[pre]) {
            pre++;
            next[suf] = pre;
            suf++;
        }else {
            if (pre > 0) {
                pre = next[pre - 1];
            }else {
                next[suf] = 0;
                suf++;
            }
        }
    }
    // 右移一位，方便KMP搜索时操作
    for (int i = len - 1; i > 0; i--) {
        next[i] = next[i - 1];
    }
    next[0] = -1;
}

int KMP(char *S, char *T) {
    int n = (int)strlen(S);
    int m = (int)strlen(T);
    int *next = malloc(sizeof(int) * m);
    buildNext(T, next);
    
    int i = 0;
    int j = 1;
    
    while (i < n && j < m) {
        if (j == 0 || S[i] == T[j]) {
            i++;
            j++;
        }else {
            j = next[j];
        }
    }
    
    if (j == m) {
        return i - m + 1 ;
    }
    return -1;
}

完整代码