2017 August 06 Dynamic-Programming, KMP

KMP 算法 - 计算子串的数量

1. 问题描述

在字符串S中寻找子串P出现的次数

2. 暴力匹配算法

在每一个位置i判断S[i, i + P.length] 是否等于P[0, P.length]，如果是则找到了一个匹配；否则就继续移动到下一个位置进行匹配。

	void BruteForceSearch(string& str, string& pattern) {
	    for (int i = 0; i < str.size() - pattern.size(); i++) {
	        int j = 0;
	        for (j = 0; j < pattern.size(); j++) {
	            if (str[i + j] != pattern[j]) {
	                break;
	            }
	        }
	        if (j == pattern.size()) {
	            cout << "Found pattern at index: " << i << endl;
	        }
	    }
	}

3. KMP算法

KMP算法的有时在于每一趟匹配结果中出现了不相等情况时，主串并不需要回溯整个P，而是找出P中前缀和后缀中最长的共有元素的位置，这样只需要回溯到重复子串第二个出现的位置即可。

如字符串S为： ABCDABABCDABCDABD
模式子串P为： ABCDABD
字符串索引： 0123456789

当i=6, j = 6时，S[i] != P[j]，可以发现子串P：“ABCDAB”有重复子串AB，因此可以认为用第二个“AB”与字符串S中出现的第二个“AB”匹配失败，所以就可以用子串P的第一个“AB”与S的第二个“AB”进行匹配。此时匹配情况如下：

字符串S：ABCDABABCD
模式子串P： ABCDABD

算法正确性证明：假设字符串S[i, i + j - 1] 与模式子串P[0, j - 1]相匹配，但是S[i + j] != P[j]，下面就要重新回溯，直到找到字符串S[i, i+j -1]中的后面几个字符与P的子串中的前几个字符相同的情况，即前面例子中S[i, i + j - 1]“ABCDAB”与P[0 , j - 1]“ABCDAB”，可以求出S的后缀与P的前缀的重复部分为“AB”。又因前面已经获知S[i, i+j - 1]与P[0, j-1]相同，所以要求的重复子串为P[0, j-1]的前缀与后缀相同的子串。求出P的前缀和后缀的最长共有元素后，当遇到S[i] != P[j]的情况时，只要将j移动到共有元素的下一个元素即可（或者是根据共有元素的长度移动）。

	void KMPSearch(string& str, string& pattern) {
	    vector<int> lps = ComputeLPS(pattern);
	    int i = 0;
	    int j = 0;
	    while (i < str.size()) {
	        if (str[i] == pattern[j]) {
	            i++;
	            j++;
	        }
	        if (j == pattern.size()) {
	            cout << "Found pattern at index: " << i - j << endl;
	            j = lps[j - 1];
	        }
	        else if (i < str.size() && pattern[j] != str[i]) {
	            if (j != 0) {
	                j = lps[j - 1];
	            }
	            else {
	                i = i + 1;
	            }
	        }
	    }
	}

4. 计算子串P前缀和后缀共有元素的长度最大值

已知LPS[i-1] = len，即在[0, i-1]中前后缀重复元素为[0, len]

如果 pattern[i] == pattern[len]，即pattern[0, i]的前后缀重复元素为[0, len+1]
如果pattern[i] != pattern[len]，表示pattern[0, i]的前后缀不存在重复元素，此时需要再缩小范围，即判断pattern[0, i]中的重复元素是否和pattern[0,len]中的重复元素相同。 ```c++ // Longest prefix suffix value for the previous vector ComputeLPS(string& str) { vector lps(str.size(), 0); int len = 0; //共有元素的长度，初始化为0 for (int i = 1; i < str.size(); ) { //如果str[i] == str[len]，则增加len if (str[i] == str[len]) { len++; lps[i] = len; i++; } else { //如果str[i] != str[len],更新len = lps[len-1] if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps; }

```