華為OJ中級問題-2つの文字列a,bの中で最も長い共通サブ列を検索する
1967 ワード
2つの文字列a,bの最長共通サブ列を検索します.
void hwOJ(){
string a = "abcdefghijklmnop";
string b = "abcsafjklmnopqrstuvw";
int lena = a.length();
int lenb = b.length();
int st1 = 0, st2 = 0,st=0;
int count = 0, MAx = 0;
string tmp = "", longStr = "";
for (int i = 0; i < lena; ++i){
for(int j = 0; j < lenb; ++j){
st1 = i; st2 = j;
while (a[st1] == b[st2]&&st1<lena&&st2<lenb){
++st1; ++st2;
++count;
}
if (count > MAx){
MAx = count;
st = i;
}
count = 0;
}
}
string str;
for (int i = 0; i < MAx; ++i){
str.push_back(a[i + st]);
}
cout << str;
}