BF算法的时间复杂度-字符串的相关知识

(3)BF算法的时间复杂度 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(n*m) 最好的情况是：一配就中！主串的前m个字符刚好等于模式串的 m个字符，只比较了m次，时间复杂度为O(m)。 最恶劣情况是：模式串的前m-1个字符序列与主串的相应字符序列比较总是相等，但模式串的第m个字符和主串的相应字符比较总是不等，此时模式串的m个字符序列必须和主串的相应字符序列块一共比较n-m+1，所以总次数为:m*(n-m+1),因此其时间复杂度为O(n×m)。