c++ KMP求两个字符串的最大公共子串
发布时间:2020-12-16 09:12:04 所属栏目:百科 来源:网络整理
导读:1 #include iostream 2 #include string 3 #include cassert 4 using namespace std; 5 6 void KMPStrMatching( string S, string P, int *N, int start, int len) 7 { 8 int j= 0 ; // 模式的下标变量 9 int i = 0 ; // 目标的下标变量 10 int pLen = P.len
1 #include <iostream> 2 #include <string> 3 #include <cassert> 4 using namespace std; 5 6 void KMPStrMatching(string S,string P,int *N,int &start,int &len) 7 { 8 int j= 0; // 模式的下标变量 9 int i = 0; // 目标的下标变量 10 int pLen = P.length( ); // 模式的长度 11 int tLen = S.length( ); // 目标的长度 12 13 while ( j < pLen && i < tLen) 14 { // 反复比较,进行匹配 15 if ( j == -1 || S[i] == P[j]) 16 i++,j++; 17 else { 18 19 j = N[j]; 20 } 21 if(j > len) { 22 len = j; start = i-j; 23 } 24 } 25 } 26 27 int* findNext(string P) 28 { 29 int j,k; 30 int m = P.length( ); // m为模式P的长度 31 assert( m > 0); // 若m=0,退出 32 int *next = new int[m]; // 动态存储区开辟整数数组 33 assert( next != 0); // 若开辟存储区域失败,退出 34 next[0] = -1; 35 j = 0; k = -1; 36 while (j < m-1) 37 { 38 if(k == -1 || P[k] == P[j]){ 39 j++; k++; next[j] = k; 40 } 41 else 42 k = next[k]; //不等则采用 KMP 递归找首尾子串 43 } 44 return next; 45 } 46 47 int main() 48 { 49 string s1 = "fffaabcdeeeeeyyyyy"; 50 string s2 = "fqbcabcmxxabcdnn"; 51 52 int istart = 0,ilen =0; 53 for(int i=0; i<s2.length(); ++i){ 54 int start = 0,len = 0; 55 KMPStrMatching(s1,s2.substr(i),findNext(s2.substr(i)),start,len); 56 if(ilen<len){ 57 ilen = len; 58 istart = start; 59 } 60 } 61 62 cout<<s1.substr(istart,ilen)<<endl; 63 64 return 0; 65 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |