首页算法

问题定义

子串的定位称为串的模式匹配，称子串T为模式串。

在串中匹配子串的最朴素的想法是移动子串头指针进行一一比对

// 起始点pos后的首个子串结束位置
int Index(std::string S, std::string T, int pos){
    int i = pos;
    int j = 0;
    while ( i <= S[0] && j <= T[0]){
        if ( S[i] == S[j] ){
            ++i;
            ++j;
        }
        else{
            i = i-j+1;
            j = 0;
        }
    }
    if ( j > T[0]){
        return i - T[0];
    }
    else return 0;
}

对于前序相同部分过长的串，这个算法的时间复杂度开销过大。比如对于模式串0001与主串00000001,需要反复遍历子串，时间复杂度为 O(m×n)\mathcal{O}(m\times n)

前缀函数

串的前缀与后缀

对于串 s[0,⋯ ,n]s[0,\cdots,n], 记 φk(s)=[0,⋯ ,k−1]\varphi_k(s)=[0,\cdots,k-1]为前缀, 记 ψk(s)=[n−k+1,⋯ ,n]\psi_k(s)=[n-k+1,\cdots,n]为后缀

前缀函数定义为串ss的前i段子串的最长的真前缀与真后缀相等的长度

π[i](s)={0i=0max⁡k{k:φk(s)=ψk(s)}i≠0\pi[i](s) = \begin{dcases} 0 & i = 0\\ \max_{k}\{k : \varphi_k(s)=\psi_k(s)\} & i\neq 0 \end{dcases}

π(s)=[π(i)[s]]\pi(s) = [\pi(i)[s]]

比如对于字符串s[acbac],它的前缀函数为

  • π[0]=0\pi[0]=0
  • π[1]=0\pi[1] = 0, 因为ac没有相等的真前缀/后缀
  • π[2]=0\pi[2] = 0, 因为acb没有相等的真前缀/后缀
  • π[3]=1\pi[3] = 1, 因为acba有相等的真前缀与后缀a
  • π[4]=2\pi[4] = 2, 因为acbac有相等的真前缀与后缀ac

因此 π(s)=[0,0,0,1,2]\pi(s)=[0,0,0,1,2]

根据这个思路实现前缀函数

#include<vector>
using namespace std;

int prefix_func_item(string s, int i){
    int res = -1;
    int n = (int) s.length();
    for (int j = i; j >= 0; j--){
            if (s.substr(0,j) == s.substr(i-j+1,j)){
                res = j;
                break;
            }
        }
    return res;
}

vector<int> prefix_func(string s){
    int n = (int) s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++){
        pi[i] = prefix_func_item(s,i);
    }
    return pi;
}

prefix_func_item的时间复杂度 O(n2)\mathcal{O}(n^2),prefix_func的时间复杂度为O(n)\mathcal{O}(n)，总时间复杂度为O(n3)\mathcal{O}(n^3), 开销巨大，需要进行优化

优化

当prefix_func 遍历到ii个元素的子串的时候，子串尾部添加元素，对前缀函数值的影响有三种可能

  1. +1+1 当添加的正好是前一位前缀函数指定的前缀的后一位元素 (比如abca -> abcab)。 翻译为数学语言: 满足s[i+1]=s[π[i](s)]s[i+1] = s[\pi[i](s)]时, π[i+1]=π[i]+1\pi[i+1] = \pi[i]+1
  2. −- 当添加的元素破坏了前缀匹配 (比如abca -> abcac / acbac -> acbaca)
  3. == 保持不变

优化1

根据情况1分析，前缀函数实际比对的是前缀段与后缀段的一小部份的子串，中间的子串段可以不遍历。而这个片段的长度上界由情况1给出 -- π[i−1]+1\pi[i-1]+1

#include<vector>
#include<string>
using namespace std;

vector<int> prefix_func(string s){
    int n = (int) s.length();
    vector<int> pi(n);
    for (int i = 0; i < n ; i++){
        for (int j = pi[i-1]+1 ; j > 0 ; j--){
            if (s.substr(0,j) == s.substr(i-j+1,j)){
                res = j;
                break;
            }
        }
    } 
    return pi;
}

优化2

当s[i+1]≠s[π[i]]s[i+1]\neq s[\pi[i]]时，前缀函数的值肯定是减少的。当子串的前缀与后缀相同的时候，可能存在子前缀与子后缀作为更小的相同片段。计算下一位前缀函数时，如果下一个元素与最大前缀的后一位元素不匹配 (即s[i+1]≠s[π[i]]s[i+1]\neq s[\pi[i]]时), 能寻找子前缀的后一位元素分析是否匹配。

子前缀的计算是递归的。对于第nn阶子前缀的长度j(n)j^{(n)}，根据上面的分析有

j(n)=π(j(n−1)−1)j^{(n)} = \pi(j^{(n-1)}-1)

例子

子串s[abcabaacabcab]相同的前缀段与后缀段为abcab,更小的子前缀/后缀段为ab(子前缀的是前缀段的相同的前缀/后缀串)。

  • 当下一位元素为a, 符合s[i+1]=s[π[i]]s[i+1]= s[\pi[i]], π[i+1]=π[i]+1=6\pi[i+1] = \pi[i]+1 = 6
  • 当下一位元素不为a时,符合s[i+1]≠s[π[i]]s[i+1]\neq s[\pi[i]], 子前缀串ab的下一位元素为c。如果子串的下一位元素为c则前缀函数π[i+1]=max⁡n{j(n)+1:s[j(n)+1]=s[i+1]}\pi[i+1] = \max_{n}\{j^{(n)}+1: s[j^{(n)+1}] = s[i+1]\}

实现

#include<vector>
#include<string>
using namespace std;
vector<int> prefix_func(string s){
    int n = (int) s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]){
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

前缀函数的时间复杂度优化到了O(n)\mathcal{O}(n)

KMP算法

对于串 ss 与待检测子串 tt, 只需要将待检测子串 tt 作为前缀进行后缀匹配就可以实现子串匹配。

#include<string>
#include<vector>
using namespace std;
vector<int> KMP(string text, string pattern){
    string cur = pattern + '#' + text;
    int s1 = text.size();
    int s2 = pattern.size();
    vector<int> res;
    vector<int> pf = prefix_function(cur);
    for ( int i = s2+1 ; i <= s1+s2; i++ ){
        if (pf[i] == s2){
            res.push_bach(i - 2*s2);
        }
    }
    return res;
}

KMP算法只用O(m+n)\mathcal{O}(m+n)的时间复杂度实现了子串在全串的匹配