最长公共子序列
1 #include2 #include 3 using namespace std; 4 5 // longest common substring(Continuous) 6 int fun(char * src, char * des) 7 { 8 int maxlen = 0; 9 int dp[105][105];10 int i,j;11 int srclen = strlen(src);12 int deslen = strlen(des);13 for(i = 0; i < srclen; i++)14 dp[i][0] = src[i] == des[0] ? maxlen = 1:0;15 for(i = 0; i < deslen; i++)16 dp[0][i] = des[i] == src[0] ? maxlen = 1:0;17 for(i = 1; i < srclen; i++)18 for(j = 1; j < deslen; j++)19 {20 dp[i][j] = src[i] == des[j] ? dp[i-1][j-1] + 1 : 0;21 maxlen = dp[i][j] > maxlen ? dp[i][j] : maxlen;22 }23 return maxlen;24 }25 // longest common substring(Discontinuous)26 // 设置墙壁好一些27 int funno(char * src, char * des)28 {29 int dp[105][105];30 int i,j;31 int srclen = strlen(src);32 int deslen = strlen(des);33 for(i = 0; i < srclen; i++)34 dp[i][0] = 0;35 for(i = 0; i < deslen; i++)36 dp[0][i] = 0;37 for(i = 1; i <= srclen; i++)38 for(j = 1; j <= deslen; j++)39 if(src[i-1] == des[i-1])40 dp[i][j] = dp[i-1][j-1] + 1;41 else42 dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];43 return dp[srclen][deslen];44 }45 int main()46 {47 char src[100];48 char des[100];49 while(cin >> src >> des)50 {51 cout << fun(src, des) << endl;52 cout << funno(src, des) << endl;53 }54 return 0;55 }
分析问题啊。