c++ KMP求两个字符串的最大公共子串_C

概述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; // 模 @H_403_6@

 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 }