![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2191W7-29.png)
文章插图
毫无疑问,对于这样的时间复杂度,105 及以上量级的数据是比较慢的 。虽然理论上BF算法时间复杂度较高,但其在实际开发中比较常用原因主要有以下2点:
(1)实际开发中,多数情况下主串与模式串长度不会很长 。对于小规模数据 , 其时间复杂度并不能代表其执行时间,某些情况下,可能比其他优化后的算法更快 。因此,尽管理论最坏时间复杂度为 O( nm ) , 但从概率统计上看 , 多数情况下其效率还是可观的 。(打比赛另说)
(2)BF 算法思想简单,实现简单 。简单意味着不容易出错 , 出错也很容易查找修改 。工程应用中,在满足性能的前提下,简单是我们的首选 。这也符合 KISS (Keep It Simple and Stupid) 设计原则 。
【思考】如果要返回所有匹配的字串首地址,该如何实现?
【参考如下】
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2193931-30.png)
文章插图
2. RK算法(Rabin-Karp)该算法算是对BF算法的优化,既然比较字符效率不高,那不如换一种比较对象 。要转换那就需要保证按照某种规则进行转换,且转换后需要保证唯一性 。对于每个字符串 , 除了它本身外有一种一般情况下唯一的表示方式,哈希值 。并且数字的比较效率要比字符高上不少;而且字符要一个一个比较,而哈希值可以代表一个串,所以比较的时候时间复杂度为 O( n ) 。
简单来说其方法思想是,在主串中每次截取和模式串一样长的字符串,获取二者的哈希值进行比较 。
【注:有关.NET/C#中的哈希及其冲突的问题 , 会在今后的文章的提到,以下均默认不会发生哈希冲突】
获取哈希值有两种方法:
(1)遍历字串中每个字符 。这样就会有许多操作:截取、遍历、计算 。但反复直接截取并没有优化时间复杂度 , 反而在一定程度上增加了时间复杂度,因为截取字符串也是一个O(n)级的操作,因此总时间复杂度依旧是O(n2)级 。我们好不容易将复杂度降低了一个量级,结果算个哈希又把量级升了回来,得不偿失 。
(2)滑动窗口 。
根据滑动窗口的原理,获取第一个串后,之后串的哈希值,可以根据移除前一个,加入后一个来实现,从而将O(n)的时间复杂度降为O(1) 。具体实现如下:
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2194Z1-31.png)
文章插图
复杂度分析:
现在,该算法第一次计算t的哈希值时,时间复杂度为O( n );后续计算哈希值因为利用了滑窗的优化只有O( 1 );比较字符串的Equals()方法,一般地,可以视为O( 1 ) 。
- 总时间复杂度为O( n )
- 空间复杂度为O( 1 )
同样,再测一下刚才的题
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2196045-32.png)
文章插图
实测时间:
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2194P7-33.png)
文章插图
可以发现,RK算法在一定程度上确实比纯暴力得BF算法效率要高,尤其是当主串长度越长时,提升越明显 。
【思考】假设有两个以行为优先主序列二维矩阵,如果要返回所有匹配的字串首地址,该如何实现?
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2195105-34.png)
文章插图
【参考如下】
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;}}}
推荐阅读
- 【前端必会】不知道webpack插件? webpack插件源码分析BannerPlugin
- 20220929-ArrayList扩容机制源码分析
- Optional源码解析与实践
- Go 源码解读|如何用好 errors 库的 errors.Is 与 errors.As() 方法
- .Net下的分布式唯一ID
- .NET 反向代理 YARP 代理 GRPC
- 赞美父亲的作文结尾 赞美父亲的高中作文
- 关于对自己有信心的名言名语 对学习有信心的名言
- 关于父亲的高中作文800字 关于父亲的高中作文
- 高一化学全面学习方法整理