基于局部最大相似设想的串匹配算法

摘要

Comparison of texts and strings are the tasks frequently appeared in the development of the application systems like automatic grading system and evaluation of the quality of data transmission system. Obviously it cannot be performed just through compare two source strings character by character. A string comparison algorithm based on local maximum similarity hypothesis is described here and which is implemented in an automatic grading system.%在设计盲打机考自动判卷系统时，需要一种有效的文本相似度判别算法。为此提出了一种基于局部最大相似设想的串匹配算法来解决此类问题，通过分别比较错误发生部位局部子字符串在插入片段、漏打片段或错打片段的的得分并选取失分最小者，实现了精确判定考生得分的目的。该算法无回溯，效率高，已应用于自动机考系统中。