论文部分内容阅读
串匹配是字符串的基本操作之一，因此为它设计一个高效算法具有一定意义。文中基于有限自动机理论，在对经典的K．M．P．算法进行分析的基础上，提出了一种快速的串匹配算法。该算法利用自动机的状态转换表实现串匹配，避免了扫描字符串时的失败链回溯，从而加快了算法的运行速度。理论分析与实验结果均表明，在正文串比较长，模式串中局部匹配失败时失败链反馈较多的情况下，该算法在速度上明显优于K．M．P．算法。但在空间复杂度上，该算法需要较多的存储空间。