从来没想过枯燥的算法居然也能上瘾。 字符串匹配是不是可以这么做,类似于hash, 但是更快
1. hash算法简化,比如取每个字符相加,
2. key长度len, 从0开始,取前len个字符hash
3. while (hash不一致 || 逐个字符比较不一致) && 没到字符串末尾
5. hash减掉当前字符,加上len+1位置字符
---------------------
3/20/2017
又想了一下,还可以改进:
相加的方法比较粗糙,基本上只有一个有效byte, 对于ab, ba很容易误判
我们可以利用寄存器长度多放几个字符,比如64位cpu, 一次可以放8个字符。
还有,hash一样对于海量数据来说是很容易发生的事情,可以引入两个或者更多的hash,计算量+1, 而冲突概率则减少了N倍。
Hash1: for(i=0;i<len;i++) hash1=hash1<<8+pattern[i]; 加减法是可逆的
Hash2: for(i=0;i<len;i++) hash2=hash1<<8^pattern[i]; 异或是可逆的
匹配的时候:
临时t_hash1=t_hash1>>>8+str[j]<<<SHIFT; 挤掉最低字符,hash上新的末尾字符
临时t_hash2=((t_hash1^str[i-1])>>>8+t_hash2<<<56) str[j]<<<SHIFT; 异或掉原来的首字符,循环左移,新的尾字符在该出现的位置上异或
这里用一个整型比较替代字符串比较,复杂度O(M+N), 需要遍历
对于长样本字符串,KMP也是个不错选择,可以根据样本尽量长的往前跳
分享到:
相关推荐
每一小节通常以对相关历史素材的讨论结束,讨论了在每一算法领域的原创研究。 本书的特点可以概括为以下几个方面: 1.概念清晰,广度、深度兼顾。 本书收集了现代计算机常用的数据结构和算法,并作了系统而深入...
每一小节通常以对相关历史素材的讨论结束,讨论了在每一算法领域的原创研究。 本书的特点可以概括为以下几个方面: 1.概念清晰,广度、深度兼顾。 本书收集了现代计算机常用的数据结构和算法,并作了系统而深入...
在压缩文件中查找字符串。 支持下列可选参数: i - 不区分大小写(默认); c - 区分大小写搜索; h - 十六进制搜索; t - 使用 ANSI, Unicode 和 OEM 字符表 (只有 Win32 可用); 如果没有指定任何参数,它...
在压缩文件中查找字符串。 支持下列可选参数: i - 不区分大小写(默认); c - 区分大小写搜索; h - 十六进制搜索; t - 使用 ANSI, Unicode 和 OEM 字符表 (只有 Win32 可用); 如果没有指定...
内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与文件夹系统操作、系统控制操作、程序...
内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与文件夹系统操作、系统控制操作、程序...
内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与文件夹系统操作、系统控制操作、程序...
内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与文件夹系统操作、系统控制操作、程序...
内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与文件夹系统操作、系统控制操作、程序...
内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与文件夹系统操作、系统控制操作、程序...
此文档包括 WinRAR 多功能综合压缩文件管理器 <br> WinRAR 功能: * WinRAR 引入了一个原创的压缩算法。它提供了比其它 PC 压缩工具更高 的压缩率,特别适用于处理可执行文件,对象库,大的文本文件...