EFFICIENT RANDOMIZED PATTERN-MATCHING ALGORITHMS
EFFICIENT RANDOMIZED PATTERN-MATCHING ALGORITHMS
复制标题
DOI：
10.1147/rd.312.0249
复制
发表时间：
1987-03-01
影响因子：
1.3
通讯作者：
RABIN, MO
中科院分区：
文献类型：
--
作者：
KARP, RM;RABIN, MO
我们提出了随机算法来解决以下字符串匹配问题及其一些推广：给定一个长度为n的字符串X（模式）和一个字符串Y（文本），找到X的第一次出现作为Y内的连续块。这些算法通过称为指纹的短得多的字符串来表示长度为n的字符串，并通过操纵指纹而不是长字符串来实现其效率。这些算法需要恒定数量的存储位置，并且基本上以真实的时间运行。它们在概念上简单，易于实现。该方法很容易推广到高维模式匹配问题。
We present randomized algorithms to solve the following string-matching problem and some of its generalizations: Given a string X of length n (the pattern) and a string Y (the text), find the first occurrence of X as a consecutive block within Y. The algorithms represent strings of length n by much shorter strings called fingerprints, and achieve their efficiency by manipulating fingerprints instead of longer strings. The algorithms require a constant number of storage locations, and essentially run in real time. They are conceptually simple and easy to implement. The method readily generalizes to higher-dimensional pattern-matching problems.