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

文章插图
毫无疑问，对于这样的时间复杂度，105 及以上量级的数据是比较慢的。虽然理论上BF算法时间复杂度较高，但其在实际开发中比较常用原因主要有以下2点：
（1）实际开发中，多数情况下主串与模式串长度不会很长。对于小规模数据，其时间复杂度并不能代表其执行时间，某些情况下，可能比其他优化后的算法更快。因此，尽管理论最坏时间复杂度为 O( nm ) ，但从概率统计上看，多数情况下其效率还是可观的。（打比赛另说）
（2）BF 算法思想简单，实现简单。简单意味着不容易出错，出错也很容易查找修改。工程应用中，在满足性能的前提下，简单是我们的首选。这也符合 KISS (Keep It Simple and Stupid) 设计原则。
【思考】如果要返回所有匹配的字串首地址，该如何实现？
【参考如下】

文章插图
2. RK算法（Rabin-Karp）该算法算是对BF算法的优化，既然比较字符效率不高，那不如换一种比较对象。要转换那就需要保证按照某种规则进行转换，且转换后需要保证唯一性。对于每个字符串，除了它本身外有一种一般情况下唯一的表示方式，哈希值。并且数字的比较效率要比字符高上不少；而且字符要一个一个比较，而哈希值可以代表一个串，所以比较的时候时间复杂度为 O( n ) 。
简单来说其方法思想是，在主串中每次截取和模式串一样长的字符串，获取二者的哈希值进行比较。
【注：有关.NET/C#中的哈希及其冲突的问题，会在今后的文章的提到，以下均默认不会发生哈希冲突】
获取哈希值有两种方法：
（1）遍历字串中每个字符。这样就会有许多操作：截取、遍历、计算。但反复直接截取并没有优化时间复杂度，反而在一定程度上增加了时间复杂度，因为截取字符串也是一个O(n)级的操作，因此总时间复杂度依旧是O(n2)级。我们好不容易将复杂度降低了一个量级，结果算个哈希又把量级升了回来，得不偿失。
（2）滑动窗口。
根据滑动窗口的原理，获取第一个串后，之后串的哈希值，可以根据移除前一个，加入后一个来实现，从而将O(n)的时间复杂度降为O(1) 。具体实现如下：

文章插图
复杂度分析：
现在，该算法第一次计算t的哈希值时，时间复杂度为O( n )；后续计算哈希值因为利用了滑窗的优化只有O( 1 )；比较字符串的Equals()方法，一般地，可以视为O( 1 ) 。

总时间复杂度为O( n )

空间复杂度为O( 1 )

这里解释一下为什么两串求得的哈希值相同还要对字符串本身进行比较。当两个串字符类型与数量相同时（如 “aaab”，”abaa” ）以这样的方式进行哈希计算，会得出相同的值，但两个字符串本身并不相同。这也是其缺点：不稳定，过于简单的计算方式或较大的数据量很容易产生哈希冲突。同时，在极端情况下，如果存在大量哈希冲突（哈希值相同，字符串本身并不相同），每次都要比较主串某一部分与模式串，那么RK算法就会退化为BF算法，时间复杂度重回 O( nm ) 。
同样，再测一下刚才的题

文章插图
实测时间：

文章插图
可以发现，RK算法在一定程度上确实比纯暴力得BF算法效率要高，尤其是当主串长度越长时，提升越明显。
【思考】假设有两个以行为优先主序列二维矩阵，如果要返回所有匹配的字串首地址，该如何实现？

文章插图
【参考如下】
RK算法比较的是字符串的哈希值，那只要获取了对应位置的哈希值，进行比较即可。对于一维，在哈希值转移时只需减去前一个、加上后一个；而二维的转移需根据模式串的规格而定。
using System;using System.Collections;using System.Collections.Generic;using System.Linq;using System.Text;using System.Numerics;using System.Diagnostics;using System.Runtime.CompilerServices;namespace Common{internal class Program{static IList<int[]> pos = new List<int[]>();static int m, n;static int p, q;static void Main(string[] args){Program pg = new();char[][] s = {new char[]{ 'c', 'a', 'b', 'c' },new char[]{ 'e', 'f', 'a', 'd' },new char[]{ 'c', 'c', 'a', 'f' },new char[]{ 'd', 'e', 'f', 'c' }};char[][] pat = {new char[]{ 'c', 'a' },new char[]{ 'e', 'f' }};m = s.Length;n = s[0].Length;p = pat.Length;q = pat[0].Length;pg.RK(s, pat);foreach (int[] arr in pos) Console.WriteLine("{ " + arr[0] + ", " + arr[1] + " }");}void RK(char[][] s, char[][] pat){int patCode = GetHash(pat, 0, 0);int sCode = GetHash(s, 0, 0);for (int row = 0; row <= m - p; row++){for (int col = 0; col <= n - q; col++){if (patCode == sCode && ComString(s, pat, row, col)) pos.Add(new int[] { row, col });if (row < m - p || col < n - q) sCode = NextHash(s, sCode, row, col);}}}int GetHash(char[][] tmp, int row, int col){int hash = 0;for (int i = row, cntR = 0; cntR < p; i++, cntR++)for (int j = col, cntC = 0; cntC < q; j++, cntC++)hash += tmp[i][j] - 'a';return hash;}int NextHash(char[][] s, int hash, int row, int col){if (row < m - p && col == n - q) return GetHash(s, row + 1, 0);for (int i = row, cntR = 0; cntR < p; i++, cntR++){hash -= s[i][col] - 'a';hash += s[i][col + q] - 'a';}return hash;}bool ComString(char[][] s, char[][] pat, int row, int col){for (int i = row, cntR = 0; cntR < p; i++, cntR++)for (int j = col, cntC = 0; cntC < q; j++, cntC++)if (s[i][j] != pat[cntR][cntC]) return false;return true;}}}