You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
36 lines
862 B
36 lines
862 B
#include<bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
/*
|
|
知识点内容：最长公共子序列
|
|
|
|
文档内容参考：
|
|
https://www.cnblogs.com/aiguona/p/7278141.html
|
|
https://blog.csdn.net/baidu_28312631/article/details/47426445
|
|
*/
|
|
char sz1[1000];
|
|
char sz2[1000];
|
|
int maxLen[1000][1000];
|
|
int main(){
|
|
while( cin >> sz1 >> sz2 ) {
|
|
int length1 = strlen( sz1);
|
|
int length2 = strlen( sz2);
|
|
int nTmp;
|
|
int i,j;
|
|
for( i = 0;i <= length1; i ++ )
|
|
maxLen[i][0] = 0;
|
|
for( j = 0;j <= length2; j ++ )
|
|
maxLen[0][j] = 0;
|
|
for( i = 1;i <= length1;i ++ ) {
|
|
for( j = 1; j <= length2; j ++ ){
|
|
if( sz1[i-1] == sz2[j-1] )
|
|
maxLen[i][j] = maxLen[i-1][j-1] + 1;
|
|
else
|
|
maxLen[i][j] = max(maxLen[i][j-1],maxLen[i-1][j]);
|
|
}
|
|
}
|
|
cout << maxLen[length1][length2] << endl;
|
|
}
|
|
return 0;
|
|
}
|