FAST STRING SEARCHING ALGORITHM
FAST STRING SEARCHING ALGORITHM
复制标题
DOI：
10.1145/359842.359859
复制
发表时间：
1977-01-01
影响因子：
22.7
通讯作者：
MOORE, JS
中科院分区：
文献类型：
--
作者：
BOYER, RS;MOORE, JS
提出了一种算法，用于搜索字符串“pat”在另一个字符串“string”中第一次出现的位置“il”。在搜索操作期间，pat 的字符从pat 的最后一个字符开始匹配。通过在模式末尾开始匹配获得的信息通常允许算法在正在搜索的文本中进行大跳转。因此，该算法具有不寻常的特性，即在大多数情况下，并非所有字符串的第一个字符都会被检查。实际检查的字符数（平均）随着 pat 长度的函数而减少。对于长度为 5 的随机英文模式，算法通常会在找到匹配项 ati 之前检查字符串的 i/4 个字符。此外，该算法的实现使得（平均而言）执行的机器指令少于i+patlen。这些结论得到了经验证据和算法平均行为的理论分析的支持。该算法的最坏情况行为是线性 ini+patlen，假设表的可用数组空间是线性 inpatlen 加上字母表的大小。
An algorithm is presented that searches for the location, “il” of the first occurrence of a character string, “pat,” in another string, “string.” During the search operation, the characters ofpatare matched starting with the last character ofpat. The information gained by starting the match at the end of the pattern often allows the algorithm to proceed in large jumps through the text being searched. Thus the algorithm has the unusual property that, in most cases, not all of the firsticharacters ofstringare inspected. The number of characters actually inspected (on the average) decreases as a function of the length ofpat. For a random English pattern of length 5, the algorithm will typically inspecti/4 characters ofstringbefore finding a match ati. Furthermore, the algorithm has been implemented so that (on the average) fewer thani+patlenmachine instructions are executed. These conclusions are supported with empirical evidence and a theoretical analysis of the average behavior of the algorithm. The worst case behavior of the algorithm is linear ini+patlen, assuming the availability of array space for tables linear inpatlenplus the size of the alphabet.