DNA片段的快速匹配算法

摘要

在基因工程中，经常需要在一个较长的DNA链中寻找一小段DNA片段．本文提出了一个新的匹配算法使得当对一个长为n的DNA链t进行检索时，在最坏的情况下克只需要比较n次就能找到一个预先给定的长为m的DNA片段户在t中所有出现的地方．而且对该算法稍加改动即可用于一般的关键字搜索（或称串匹配）．在同类算法中，该算法可能是迄今为止最有效的．