数据结构与算法总结：字符串（KMP模式匹配算法）_字符串特征向量

字符串

1. 常用标准串函数

String类里面的函数：

2. 字符串的模式匹配（Pattern matching）

​ 所谓模式匹配，是指在文本T（text）中寻找一种特定的模式P（pattren），比如PDF等文档文件中常用的“查找”操作。

​ 模式匹配又分 精准匹配 和 近似匹配 两种。

2.1. 朴素的模式匹配算法

​ 基本思想是将P从T的开始进行匹配，如果“失配”则向后移动一位。

int NaiveStrMatching(const string T, const string P){
    int i = 0;//P的索引
    int j = 0;//T的索引
    int len_i = P.length();
    int len_j = T.length();
    
    if(len_i >= len_j) return -1;
    while(i<len_i && j<len_j){
        if(T[j]==P[i]){
            j++;i++;
        }
        else{
            j = j-i+1;
            i = 0;
        }
    }
    if(i>=len_i) return j-i+1;
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

​ 若设P的长度为M，T的长度为N。该算法最差的时间复杂度为O(M*N).

2.2. KMP模式匹配算法

字符串的特征向量

​ 在朴素的模式匹配算法中，存在大量没有必要的回溯。如下图中，在T[3]处发生失配，按照朴素的模式匹配法，会将P一步步移动至完全匹配，且每次匹配都会从头开始匹配。但这并不是必要的，我们完全可以直接将P移动到失配的位置开始匹配。

​ KMP算法通过定义next数组来计算发生失配时，应从P的哪个位置继续匹配。在KMP算法中，不存在T的回溯。next[i]定义如下为子串P[0:i]（不包括P[i]）的前缀子串与后缀子串的最大匹配数。且定义next[0] = -1。比如：

​ 另一种对next数组更好的理解是，当P[i]与T[j]发生失配时，应使用P[next[i]]来与T[j]进行匹配。（根据next[i]的定义可知，next[i]之前的位置肯定是能匹配上的，不需要再对j进行回溯）。

​ 求解next数组的方法如下：

//求next数组
int *findNext(string P){
    int i = 0;
    int k = -1;
    int len = P.length();
    int *next = new int [len];
    next[0] = -1;
    while(i < len-1){	//注意不是i < len.
		while(k != -1 && P[i]!=P[k]){
            k = next[k];
            //这一段看了好久才理解。这其实也是一个KMP的模式匹配，是P的前缀与P的后缀的匹配。
        }
        i++;
        k++;
        next[i]=k;
        //注意next的定义是i之前的最大前缀后缀匹配数，所以i要加一；由于P[i]==P[k]，所以要加一
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

​ 这种next的定义仍有不好的地方。当碰到连续相同的字母时，时间消耗会增加。比如如下情况：

​ 这种时候，很明显由于P[2]==P[0]，而P[2]失配，所以P[2]必然失配，所以完全可以直接跳到next[2].

​ 优化的next数组的求解如下（此时的next的定义不再是前缀后缀匹配数，而是当i处失配时，应和T[i]进行匹配的元素）：

//优化的next数组的求算
int* findNext(string P){
    int i = 0;
    int k = -1;
    int len = P.length();
    next[0] = -1;
    while(i<len-1){
        while(k!=-1 && P[i]!=P[k]){
            k = next[k];
        }
        i++;
        k++;
        if(P[i]==P[k]){
            next[i] = next[k];//优化
        }
        else{
            next[i] = k;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

KMP模式匹配算法

int KMPStrMatching(string T, string P, int* next){
    int i = 0;
    int j = 0;
    int lenp = P.string();
    int lent = T.string();
    if(lent < lenp) return -1;
    while(i < plen && j < tlen){
        if(i==-1 || P[i]==P[j]){
            i++;j++;//i=-1的时候，意味着与j匹配永远是失败的。直接从j+1开始重新匹配。
        }
        else{
            i = next[i];
        
    }
    if(i == plen){
        return j - plen + 1;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19