華為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;
}