3、BF算法的时间复杂度 讨论: 若n为主串长度,m为子串长度,则串的BF匹配算法最坏的情况 下需要比较字符的总次数为(n-m+1)m=O(m) 最好的情况是:一配就中!只比较了m次。 最恶劣情况是:主串前面n-m个位置都部分匹配到子串的最后 一位,即这nm位比较了m次,别忘了最后m位也各比较了 次,还要加上m!所以总次数为:(n-m)*m+m=(n- 影苦莉用己部分匹配过的信息而加快模式串的滑动速度? 能!而且主串S的指针必回溯!最坏情况也能达到o(n+m) 请看KMP算法!4 3、BF算法的时间复杂度 讨论： 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况 下需要比较字符的总次数为(n-m+1)*m＝O(n*m) 最好的情况是：一配就中！ 只比较了m次。 最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后 一位，即这n-m位比较了m次，别忘了最后m位也各比较了 一次，还要加上m！所以总次数为：(n-m)*m+m ＝(n￾m+1)*m 能否利用已部分匹配过的信息而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m) 请看KMP算法！