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

Question

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

A．O(1)

B．O(n)

C．O(n2)

D．0(n3)

Answer 1

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