KMP

前缀函数

1 概述

  前缀指字符串 str 中由起始位到某一位结束的子串，即前缀prefix(str, i) = s[0,...,i]。真前缀则是不包括当前位的字符。

  后缀是由字符串str 中某一位到串尾的子串，与真前缀一样，真后缀同样不包括当前位的字符。

2 前缀函数

  给定一个长度为 n 的字符串 ，其 前缀函数 被定义为一个长度为 n 的数组 $\pi$。 其中 $\pi$[i] 的定义是：

1. 如果子串 s[0, 1, ..., i] 有一对相等的真前缀 s[0, ..., k-1] 和真后缀s[i-(k-1), ..., i] , 那么 $\pi$[i] 就是这个真前缀的长度；如果有多对相等的真前缀和真后缀，则 $\pi$[i] 为这些子串中的最长长度。
2. 如果没有相等的真前缀和真后缀，则 $\pi$[i] 定义为 0 .

如字符串str = "abcabcd" , 则其前缀函数为："prefix = [0, 0, 0, 1, 2, 3, 0]".
而字符串str1 = "aabaaab" 的前缀函数则为：prefix = [0, 1, 0, 1, 2, 2, 3].

3 代码实现

• 求取前缀函数的朴素实现：

  首先申请一个容量等于字符串长度的 vector 并初始化为0, 从下标为 1 开始对字符串进行遍历(前缀函数规定是当前子串中那对最长的相等的真前缀和真后缀的长度，而下标为 0 的子串没有不同时存在真前缀和真后缀，因而为 0), 内循环中 j 从最大真前缀长度开始 ，遇到有相等的真前缀和真后缀则直接对前缀函数对应位赋值并进行下一个子串的计算。

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

此时算法的时间复杂度为 O($n^3$).

• 优化1：

易知：当移动到下一位置时，前缀或加 1 , 或不变，或减少。

vector<int> prefix_fn(string s){
    n = s.length();
    vector<int> res(n,0);
    for(int i = 1; i < n; ++i){
        for(int j = res[i-1]; j >= 0; --j){     //只有这里进行修改
            if(s.substr(0, j) == s.substr(i-j+1, i)){
                res[i] = j;
                break;
            }
        }
    }
    return res;
}

此时的时间复杂度为 O($n^2$).

• 优化2：

vector<int> prefix_fn(string s){
    n = s.length(); 
    vector<int> res(n,0);
    for(int i = 1; i < n; ++i){
        int j = res[i-1];
        while(j>0 && s[j] != s[i]) j = res[j-1];
        if(s[i] == s[j]){
            ++j;
        }
        res[i] = j;
    }
    return res;
}

此时的时间复杂度为 O($n$).

4 应用：KMP算法

考虑目标字符串 ptr : ababaca. 字符串长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。

• 求next数组

vector<int> calNext(string str){
    int len = str.length();
    vector<int> res(0, len);
    res[0] = -1;    //next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    int k = -1;     //k初始化为-1
    for(int i = 1; i < len; ++i){
        while(k > -1 && str[i]!=str[k]){//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。
            k = res[k]; //往前回溯
        }
        if(str[i] == str[k+1]){
            ++k;    //如果相同，k++
        }
        res[i] = k; //这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]    
    }
    return res;
}

• KMP算法

vector<int> calNext(string pattern, string str){
    int len1 = pattern.length(), len2 = str.length();
    vector<int> next = calNext(pattern);
    int k = -1;
    for(int i = 0; i < len2; ++i){
        while(k > -1 && str[i] != pattern[k]){//pattern和str不匹配，且k>-1（表示pattern和str有部分匹配）
            k = next[k];    //往前回溯
        }
        if(str[i] == pattern[k+1]){
            ++k;
        }
        if(k == len1 - 1){  //说明k移动到ptr的最末端
            return i - k + 1;   //返回相应的位置
        }
    }
    return res;
}