字符串匹配算法

假设主串（文本串）是一个长度为 \(n\) 的字符串 \(A\)，子串（模式串）是一个长度为 \(m\) 的字符串 \(B\)，我们的目的是要从 \(A\) 中匹配到 \(B\)

BF 算法

最朴素的串模式匹配算法

逻辑梳理

滑动窗口的做法

设主串（文本串） \(A\) 匹配到 \(i\) 位置，子串 \(B\) 匹配到 \(j\) 位置

如果 \(A[i]=B[j]\)，\(i++,j++\)，继续匹配下一个字符
如果 \(A[i]\ne B[j]\)，\(i=i-(j-1),j=0\)，也就是失配就回溯

代码实现

int BF(string A, string B){
    int n = A.size();
    int m = B.size();
    for(int i = 0; i <= n - m; ++i) {
        string temp = A.substr(i, m);
        if(temp == B) return i;
    }
    return -1;
}

int BF(string A, string B) {
    int n = A.size();
    int m = B.size();
    // 滑动窗口
    for(int i = 0; i <= n - m; ++i) {
        int j = 0;
        while (j < m && A[i + j] == B[j]) j++;
        if (j == m) return i;
    }
    return -1;
}

优点：不需要预处理，固定存储空间，算法复杂度 \(O(mn)\)

缺点：最坏复杂度高

KR 算法

将 \(m\) 个字符的比较变为一个哈希值的比较

算法效率取决于哈希函数的选取

定义哈希函数 \(f(s)=\Sigma_{i=1}^{n}\times k^{n-i}(\text{mod} p)\) 或者 \(f(s)=\Sigma_{i=1}^{n}\times k^{i}(\text{mod} p)\)

其中 \(k\) 为一个整数，\(p\) 为一个大整数

冷知识：实际使用时只取后几位的二进制的哈希函数

代码实现

int KR(string A, string B){
    int n = A.size();
    int m = B.size();
    
    int k = 256; // 基数
    int p = 1000000007; // 大质数
    long long B_hash = 0;
    for(int i = 0; i < m; ++i) B_hash = (B_hash * k + B[i]) % p;
    
    long long At_hash = 0;
    long long power = 1; // 用于存储 k^(m-1) mod p
    
    for(int i = 0; i < m; ++i){
        At_hash = (At_hash * k + A[i]) % p;
        if(i < m-1) power = (power * k) % p;
    }
    
    // 滑动窗口
    for(int i = 0; i <= n-m; ++i){
        if(B_hash == At_hash) return i;
        /*
        // 避免 hash 冲突
        if(B_hash == At_hash){
        	bool key = true;
        	for(int j = 0; j < m; ++j){
        		if(A[i+j] != B[j]){
        			key = false;
        			break;
        		}
        	}
        	if(key) return i;
        }
        */
        if(i < n-m){
            At_hash = (At_hash - A[i] * power % p + p) % p;
            At_hash = (At_hash * k + A[i+m]) % p;
        }
    }
    return -1;
}

KMP 算法

KMP 算法发现每个字符对应的该 \(k\) 值仅依赖于模式 \(B\) 本身，与目标对象 \(A\) 无关

逻辑梳理

设主串（文本串） \(A\) 匹配到 \(i\) 位置，子串 \(B\) 匹配到 \(j\) 位置

如果 \(j=-1\) 或者 \(A[i]=B[j]\)，\(i++,j++\)，继续匹配下一个字符
如果 \(j\ne -1\) 且 \(A[i]\ne B[j]\)，\(i\) 不变，\(j=next[j]\)
这一步相当于子串向右移动实际位数为 \(j-next[j](\ge 1)\)

前缀函数

长度为 \(n\) 的字符串 \(s\) 前缀函数为数组 \(next\)

其中 \(next[i]\) 定义为字串 \(s[0...i]\) 最长的相等的真前缀和真后缀的长度

即 \[next[i] = \max\{k=0...i}\\{k:s[0...k-1]=s[i-(k-1)...i]\}\]

规定 \(next[0]=-1\)

\(e.g.\)：字符串 \(abcabcd\)

\(next[4]=2\space\) \(abcab\) 最长相等的真前缀真后缀为 \(ab\)

\(next[5]=3\space\) \(abcabc\) 最长相等的真前缀真后缀为 \(abc\)

\(next[6]=0\space\) \(abcabcd\) 无相等的真前缀真后缀

计算前缀函数的方法

推导：如果第 \(i\) 位失配时，怎么求 \(next[i]\)

如果 \(A[i]==A[k]\) 显然 \(next[i+1] = k+1\)
如果 \(A[i]!=A[k]\)
由 \(next\) 数组的含义，我们知道 \(k = next[i]\)
\(p=A[0,..,k-1]\) 与 \(q=A[i-k,...i-1]\) 相等的，记此时 \(C=A[0,...i-1]\)
此时 \(p\) 的最长真前缀真后缀相等的字符串与 \(q\) 的最长真前缀真后缀相等的字符串相同，记这个字符串为 \(r\)
\(r\) 是 \(p\) 的真前缀，那么它是 \(C\) 的真前缀，\(r\) 是 \(q\) 的真后缀，那么它是 \(C\) 的真后缀
假如存在一个比 \(r\) 长的 \(C\) 的既是真前缀也是真后缀的字符串，记为 \(r'\)
那么 \(r'\) 是 \(p\) 的真前缀，\(q\) 的真后缀，由 \(p=q\) 知 \(r'\) 是 \(p\) 的真后缀，这与 \(r\) 的最大性矛盾，故 \(r\) 是 \(C\) 最长的相等的真前缀真后缀字符串
根据 \(next\) 数组的含义 \(next[i]=r.size()\)
容易知道 \(next[k]=r.size()\)，那么 \(k = next[i]=r.size()=next[k]\)
当 \(k == -1\) 时 \(next[++i]=0\)，和第一种情况合并

vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n-1){
        if(k == -1 || s[i] == s[k]) next[++i] == ++k;
        else k = next[k];
    }
    return next;
}

\(next\) 数组含义：

当前字符串中，最大长度相同真前缀和真后缀
发生失配时，下一步匹配时子串跳到的位置，如果 \(next[j]=k>0\)，则跳到子串的 \(k\) 位置\((next[j])\)

KMP 算法的多次匹配

如果要搜索的字符串匹配段有重叠的情况，匹配成功时，子串后移整个子串的最大公共真前缀和真后缀长度，和文本串的下一位继续匹配

代码实现

单次匹配

vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n+1);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n){
        while(k != -1 && s[i] != s[k]) k == next[k];
        ++i;++k;
        if(s[i] == s[k]) next[i] = next[k];
        else next[i] = k;
    }
    return next;
}

int KMP(string A, string B){
    int n = A.size();
    int m = B.size();
    vector<int> next = getNext(A);
    int i = 0,j = 0;
    while(i < n){
        while(j != -1 && A[i] != B[j]) j = next[j];
        ++i;++j;
        if(j >= m) return i - j;
    }
    return -1;
}

多次匹配

vector<int> getNext(string s){
    int n = (int)s.size();
    vector<int> next(n+1);
    int k = -1; // preNext=-1;
    next[0] = -1;
    while(i < n){
        while(k != -1 && s[i] != s[k]) k == next[k];
        ++i;++k;
        if(s[i] == s[k]) next[i] = next[k];
        else next[i] = k;
    }
    return next;
}

int KMP(string A, string B){
    int n = A.size();
    int m = B.size();
    vector<int> next = getNext(A);
    int i = 0, j = 0, ans = 0;
    while(i < n){
        while(j != -1 && A[i] != B[j]) j = next[j];
        ++i;++j;
        if(j >= m){
            ++ans;
            j = next[j];
        }
    }
    return ans;
}

预处理需要 \(O(m)\) 的时间和空间

算法时间复杂度 \(O(n+m)\)

查找阶段最大比较次数 \(2n-1\)

热知识：实际运用中 KMP 算法会比 BM 算法慢

冷知识：实际运用中 KMP 算法绝大多数情况会比 BF 算法慢

为 KMP 算法定制的字符数据中绝大多数情况会比 KR 算法慢

KMP 可以在 AC 自动机（KMP + Trie 树）中使用

BM算法

从右向左匹配字串

两大启发式规则：

坏字符规则：利用第一个不匹配的字符（坏字符）在子串中的位置信息，尝试进行大跨度跳跃，目标是对齐可能匹配的字符
好后缀规则：利用匹配成功的后缀的信息，尝试进行大跨度跳跃，目标是对齐可能匹配的后缀子串

待整理

最后出现位置表——BC 表

预处理需要 \(O(m+\Sigma)\) 的时间和空间

算法时间复杂度最坏为 \(O(m+n)\)，最好为 \(O(\frac{n}{m})\)

Galil 规则

STL 中的字符串匹配算法

待整理

(´-ω-｀)

字符串匹配算法

BF 算法

逻辑梳理

代码实现

KR 算法

代码实现

KMP 算法

逻辑梳理

前缀函数

KMP 算法的多次匹配

代码实现

BM算法

最后出现位置表——BC 表

Galil 规则

STL 中的字符串匹配算法