KMP算法-串的匹配问题

待解决的问题

串的模式匹配问题 给定一个主字符串（以S代替）和模式串（以P代替），要求找出P在S中出现的位置 假定S长度为n，P长度为m。

方法一：暴力匹配（朴素字符串匹配）

思想：遍历S的每个字符，以该字符为始与P比较，全部匹配就输出相应的位置；否则直到S结束时间复杂度：O(n*m)代码 //朴素字符串匹配（暴力匹配）算法 #include<iostream> #include<string> using namespace std; int NativeStringSearch(string S, string P) { int i = 0; //S的下标 int j = 0; //P的下标 int s_len = S.size(); int p_len = P.size(); while(i < s_len && j < p_len) { if(S[i] == P[j]) //若相等个，都前进异步 { i++; j++; }else{ //不相等 i = i-j+1; j = 0; } } if( j == p_len) return i-j; //匹配成功，返回匹配的位置 return -1; //-1表示匹配失败 } int main() { cout<<NativeStringSearch("BBC ABCDAB ABCDABCDABDE","ABCDABD")<<endl; return 0; }

方法二 KMP字符串匹配算法

思想 当遇到不匹配的字符时，不是往后移动一个字符，而是利用一个next数组，来找到下一次的比较位置，以此来跳过一些没有意义（或者说之前比过）的字符。即利用已经得到的部分匹配信息来进行后面的匹配过程 next[j] 是用来保存 P[0]至P[j-1]中最长的相同前后缀的长度。时间复杂度： O(n+m)代码 #include<iostream> #include<string> using namespace std; /*P为模式串，下标从0开始*/ //得到next[]数组,next[j] 是用来保存 P[0]至P[j-1]中最长的相同前后缀的长度 void GetNext(string P, int next[]) { int p_Len = P.size(); int i = 0; //P的下标 int j = -1; //相同前后缀的长度 next[0] = -1; while(i < p_Len) { if( j==-1 || P[i]==P[j]) { i++; j++; next[i] = j; }else{ j = next[j]; } } } int KMP(string S, string P, int next[]) { GetNext(P,next); int i = 0; //S的下标 int j = 0; //P的下标 int s_len = S.size(); int p_len = P.size(); while( i<s_len && j<p_len) { if( j == -1 || S[i] == P[j]) //P的第一个字符不匹配 或 S[i]==P[j] { i++; j++; } else { j = next[j]; //当前字符串匹配失败，进行跳转 } } if( j == p_len) return i-j; return -1; } int main() { int next[100] = { 0 }; cout<<KMP("BBC ABCDAB ABCDABCDABDE","ABCDABD",next)<<endl; return 0; }

未完待续~

参考

参考地址