问答题 模式匹配算法是在主串中快速寻找模式的一种有效的方法,如果设主串的长度为m,模式的长度为n,则在主串中寻找模式的KMP算法的时间复杂性是多少?如果某一模式’P=-"abcaacabaca",请给出它的NEXT。函数值及NEXT函数的修正值NEXTVAL之值。【上海交通大学2000一(5分)】
【正确答案】正确答案:KMP算法的时间复杂度是O(m+n)。P的NEXT和NEXTVAL值分别为011 12212321和01 102201320。
【答案解析】