标签归档:字符串匹配算法

有限自动机的字符串匹配

自动机虽然是通过很多数学知识来论证其正确性,但是其原理确很简单。这里通过加回忆之前的学习,简单介绍下自动机的字符串匹配原理。自动机的字符在完成前期的工作后,其字符串的匹配时间复杂度为O(n),其中n为目标串的字符数,即自动机的匹配搜索不需要回溯,其如何完成避免回溯工作的呢? 继续阅读