1.概述 在讲解KMP匹配算法之前,我们不妨来看看我们用暴力法是怎么完成字符串的匹配的. 在我们的目标串T:101011011,和模式串P:110中,我们在T中找寻P第一次出现在T中的下标.通过上图,我们发现我们利用暴力匹配法,在某次失败后我们只能非常机械的一步一步移动我们的模式串P.所以我们理解了上述过程后,不难写出如下的匹配代码:
int match_1(const char* T,const char* P) { int n = strlen(T); int m = strlen(P); for(int i=0;i<n-m+1;i++) { for(int j=0;j<m;j++) { if(T[i+j] != T[j]) break; if(j>=m) return i; } } } int match_2(const char* T,const char* P) { int n = strlen(T); int m = strlen(P); for(int i=0,j=0;i<n&&j<m;) { if(T[i]==P[j]) { i++; j++; } else{ //匹配失败,回溯 j = 0; i = i-j+1; //比之前,向前一步 } } }总结 虽然暴力字符串匹配算法实现起来非常简单,然而我们并不能满足于此,分析时间复杂度我们知道,在最坏情况下,每次我们都是在最后一次失败,所以为(m-1 + 1)步,和我们需要移动(n-m+1)次,所以暴力匹配的时间复杂度为,O(n*m);虽然说n>>m,但这确实还能进行优化.
KMP匹配算法是上图三位于1977年共同发现.KMP匹配就是利用之前已经成功匹配,借助成功的经验,来加速向右移动.
//待完成,见谅.
