A comparison of three string matching algorithms
作者:
G. De V. Smit,
期刊:
Software: Practice and Experience
(WILEY Available online 1982)
卷期:
Volume 12,
issue 1
页码: 57-66
ISSN:0038-0644
年代: 1982
DOI:10.1002/spe.4380120106
出版商: John Wiley&Sons, Ltd.
关键词: Pattern matching;String matching;Searching;Time complexity
数据来源: WILEY
摘要:
AbstractThree string matching algorithms—straightforward, Knuth‐Morris‐Pratt and Boyer‐Moor—re examined and their time complexities discussed. A comparison of their actual average behaviour is made, based on empirical data presented. It is shown that the Boyel‐Moore algorithm is extremely efficient in most cases and that, contrary to the impression one might get from the analytical results, the Knuth‐Morris‐Pratt algorithm is not significantly better on the average than the straightfo
点击下载:
PDF
(462KB)
返 回