拉宾-卡普算法 在计算机科学中拉宾卡普算法英語RabinKarp algorithm或卡普拉宾算法KarpRabin algorithm是一种由理查德卡普与迈克尔拉宾于年提出的使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配该算法先使用旋转哈希以快速筛出无法与给定串匹配的文本位置此后对剩余位置能否成功匹配进行检验此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配 若要在一段文本中找出单个模式串的一个匹配此算法具有线性时间的平均复杂度其运行时间与待匹配文本和模式串的长度成线性关系虽然平均情况下此算法表现优异但最坏情况下其复杂度为文本长与模式串长的乘积当在文本中搜寻多个匹配时其具有线性时间的平均复杂度与文本串长模式串长模式串所有匹配总长三者的和成线性关系相对地另一种用于找出模式串所有匹配的AC自动机算法的最坏情况复杂度与文本串长模式串长模式串所有匹配总数而非总长成正比 此算法的一个实际应用为内容相似度检验英语content similarity detection如论文查重在给定原材料与待查重论文的情况下此算法可以迅速在论文中搜寻原材料中的句子同时忽略诸如大小写与标点等细节由于原材料中的字符串过多故单字符串搜索算法在此处不适用