背景

精确字符串搜索算法最简单的是Brute-Force，本次比较失败，则下次仍从模式串起始字符按顺序遍历“待匹配字符串”，但时间复杂度极高。著名的KMP（ Knuth-Morris-Pratt ）算法是经典的字符串搜索算法，充分利用失败信息，尽量增加下一次匹配索引，以此减少总的匹配次数，针对单条“待匹配字符串”具有较低的时间复杂度。但当需要匹配大量固定的“待匹配字符串”时，采用KMP算法的执行时间将与“待匹配字符串”数量成正比，进而仍然具有较高的时间复杂度。

本文，通过“抽取定长索引”及“定序比较索引”的方式，实现了一种内存保护的大规模精确串字符串搜索算法。

怎么实现的？

本文提出一种内存保护的大规模精确字符串搜索算法，采用“抽取定长索引”及“定序比较索引”的方式，在保证不出现内存溢出错误的前提下，执行时间较短，搜索性能较高。系统模块设计分为三部分：定长子串抽取、索引树构建、索引定序比较。

   A）定长子串抽取，用于抽取“原始待匹配字符串”为“定长子串”。

将（所有）原始待匹配字符串抽取为多个定长子串，前面的子串均为定长，最后几个子串长度会逐渐减小。例如：原始待匹配字符串为“aliyunlanyan”，最大定长为3，最小定长为2，最大索引串数量为3，原始待匹配字符串抽取为3个定长子串“ali”、“yun”、“lan”。

   B）索引树构建，利用已划分的“定长子串”集合构建内存可控的索引树。

根据定序字符串所含字符的先后顺序构造索引树，字符转换为树节点间的跳转边。但是需要同步记录树节点在“待匹配字符串”中的索引。索引树本质上是一个AC（Aho-Corasick automation）自动机，构建完正确跳转，还需要构建失败跳转。

由于限定了所有“定长子串”的长度，因此限定了索引树的最大深度，进而控制了索引树的内存空间。

索引树实例参照：

   C）全量索引比较。使用“索引树”扫描“模式串”得到匹配成功的“待匹配字符串”集合。

使用“索引树”扫描“模式字符串”，得到“候选待匹配字符串successMatchString”及其“待匹配字符串索引集合indexSet”，直到“模式串”没有剩余字符则结束，此时符合要求的“候选待匹配字符串successMatchString”，即为过滤成功的“待匹配字符串”。

（1）创建存储“候选待匹配字符串匹配进度的映射successMatchStringMap”,键为“待匹配字符串successMatchString”，值为“待匹配字符串索引集合indexSet”。

（2）“模式字符串”逐个字符遍历“索引树”，currentAcState表示当前当前字符对应的AC状态机的状态。则判断此状态currentAcState是否存在“候选待匹配字符串successMatchString”。

如果存在，则将此状态对应的能够匹配的“候选待匹配字符串successMatchString”添加到“候选待匹配字符串匹配进度的映射successMatchStringMap”，并同步更新“待匹配字符串索引集合indexSet”。如果此时“待匹配字符串索引集合indexSet”的长度等于“候选待匹配字符串successMatchString”的定长子串的总数，则 “候选待匹配字符串successMatchString”，即为过滤成功的“待匹配字符串”，如果采用子串函数进一步验证成功，则表示匹配成功，返回结果true。

（3）重复步骤（2），直到“模式字符串”遍历结束，则表示匹配失败，返回结果false。

    内存保护的大规模精确字符串搜索算法参照：

有哪些实际价值？

1）内存利用率高：采用原始待匹配字符串划分得到的“定长子串”构建内存利用率较高的索引树，避免了模式匹配程序出现内存溢出错误。

2）匹配性能好：采用“定序比较模式子串”方式，具有不强依赖于待匹配字符串集合数量的特性，具有较好的匹配性能。