问题
单项选择题
若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。
A．O(1)
B．O(n)
C．O(n2)
D．0(n3)
答案
参考答案：C
解析：[分析] 在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n2。
搜题请搜索小程序“爱下问搜题”
若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。
A．O(1)
B．O(n)
C．O(n2)
D．0(n3)
参考答案：C
解析：[分析] 在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n2。