.NET源码学习 [算法2-数组与字符串的查找与匹配]( 十 ) _生活百科

文章插图
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
代码实现：【注：考虑到时间成本与篇幅问题，在此不做BM算法的同意主串多次匹配问题，如有兴趣欢迎自行研究，本人也可能会在今后放出可对同一主串多次匹配的代码】

文章插图
复杂度分析：

时间复杂度为O( n ) 若模式串中包含大量重复字符，则计算两个数组的时间将会达到 O( m2 )，但一般不会出现这样的极端情况。

空间复杂度为O( m )

文章插图
这就是一种极端情况，存在大量重复字符，导致其效率严重下降。
总结—— —— —— —— —— —— —— —— —— —— —— —— —— ——
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
至此，四种匹配方法全部介绍完毕，总结一下：
1. BF纯暴力算法，一位以为比较，遇到不匹配的从模式串开头在此一位一位比较。时间复杂度较高，但简洁明了思路清晰，因此在实际应用中最为常用。
2. RK算法，基于BF的比较字符的思想，转化为比较子串的哈希值。数值间的比较确实比字符比较快，而且利用滑窗的思想将计算哈希的时间复杂度将为 O( n ) ，但容易存在哈希冲突的问题，冲突后需要对两部分子串进行完整比较。计算哈希方式越简单、字符串越长，冲突的概率越高，复杂度也会接近 O( n2 ) 。
3. KMP算法，利用某一特殊的规律，减少在不匹配时向后退回的位数，以达到降低时间复杂度的目的。
4. BM算法，结合贪心思想，进一步对KMP进行优化。但这两种方法过于复杂，掌握很不容易。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
[附 BF算法代码]void BF(string s, int n, string pat, int m){for (int i = 0; i <= n - m; i++){int j = 0;while (j < m){if (s[i + j] != pat[j]) break;j++;}if (j == m) pos.Add(i);}}[附 RK算法代码]void RK(string s, int n, string pat, int m){int patCode = GetHash(pat);int sCode = GetHash(s.Substring(0, m));for (int i = 0; i <= n - m; i++){if (patCode == sCode && ComString(i, s, pat)) pos.Add(i);if (i < n - m) sCode = NextHash(s, sCode, i, m);}}int GetHash(string str){int hash = 0, n = str.Length;for (int i = 0; i < n; i++) hash += str[i] - 'a';return hash;}int NextHash(string str, int hash, int idx, int len){hash -= str[idx] - 'a';hash += str[idx + len] - 'a';return hash;}bool ComString(int idx, string s, string pat){return pat == s.Substring(idx, pat.Length);}[附 KMP算法代码]void KMP(string s, int n, string pat, int m){next = GetNext(pat, m);int j = 0;for (int i = 0; i < n; i++){while (j > 0 && s[i] != pat[j]) j = next[j];if (s[i] == pat[j]) j++;if (j == m){pos.Add(i - m + 1);j = next[j - 1];}}}int[] GetNext(string pat, int m){next = new int[m];int j = 0;for (int i = 1; i < m; i++){while (j != 0 && pat[j] != pat[i]) j = next[j];if (pat[j] == pat[i]) j++;next[i] = j;}foreach (int i in next) Console.Write(i + " ");return next;}[附 BM算法代码]static int SIZE = 26;void GenerateGS(string pat, int m, int[] suffix, bool[] prefix) // 预处理{suffix = new int[m];prefix = new bool[m];Array.Fill(suffix, -1);Array.Fill(prefix, false);for (int i = 0; i < m - 1; i++){int j = i, k = 0; // k 为公共子串的长度while (j >= 0 && pat[j] == pat[m - k - 1]) // 与 b[ 0, m - 1 ]求公共后缀子串{j--;k++;suffix[k] = j + 1; // j + 1 表示公共后缀子串在 pat[ 0, i ] 中的起始下标}if (j == -1) prefix[k] = true; // 公共后缀子串也就是模式串的前缀子串}}void GenerateBC(string pat, int m, int[] table) // 建立哈希表{for (int i = 0; i < SIZE; i++) table[i] = -1;for (int i = 0; i < m; i++) table[pat[i] - 'a'] = i;}int MoveByGS(int j, int m, int[] suffix, bool[] prefix){int k = m - j - 1;if (suffix[k] != -1) return j - suffix[k] + 1;for (int r = j + 2; r < m; r++)if (prefix[m - r] == true) return r;return m;}int BM(string s, int n, string pat, int m){s = s.ToLower();pat = pat.ToLower();int[] table = new int[SIZE];GenerateBC(pat, m, table); // 构建坏字符哈希表int[] suffix = new int[m];bool[] prefix = new bool[m];GenerateGS(pat, m, suffix, prefix);int i = 0;// i 表示主串与模式串上下对齐的第一个字符while (i <= n - m){int j;for (j = m - 1; j >= 0; j--) // 从后向前匹配if (s[i + j] != pat[j]) break; // 坏字符对应下标为 jif (j < 0) return i; // 匹配成功int x = j - table[s[i + j] - 'a']; // 向后滑动int y = 0;if (j < m - 1) y = MoveByGS(j, m, suffix, prefix);i += Math.Max(x, y);}return -1;}