若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

admin2010-05-13 39

问题若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

选项 A、O(1)
B、O(n)
C、O(n²)
D、0(n3)

答案4

解析在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n²。

转载请注明原文地址:https://kaotiyun.com/show/USSZ777K

三级数据库技术

相关试题推荐

随机试题

最新回复(0)