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

—— —— —— —— —— —— —— —— —— —— —— —— —— ——
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
[附 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;}[# 有关Intrinsic、Attribute与“内在属性”]