编辑代码

#include <iostream>
#include <string>

using namespace std;
int fun(string str1, string str2, string* Subsequence);



int main() {
    string str1 = "cup";
    string str2 = "ktv";

    string bestseq="";

    int length = fun(str1, str2, &bestseq);

    cout << "最长为 " << length << endl;
    cout << bestseq << endl;

     str1 = "pyt";
     str2 = "put";

      bestseq = "";

     length = fun(str1, str2, &bestseq);

    cout << "最长为 " << length << endl;
    cout << bestseq << endl;
    str1 = "api";
    str2 = "apple";

    bestseq = "";

    length = fun(str1, str2, &bestseq);

    cout << "最长度为 " << length << endl;
    cout << bestseq << endl;
    return 0;
}
int fun(string str1, string str2, string* Subsequence)
{

    int length1 = str1.length();
    int length2 = str2.length();
    int** Array = new int* [length1];
    for (int i = 0; i < length1; i++) {
        Array[i] = new int[length2];
    }

    int maxlength = 0;
    for (int i = 0; i < length1; ++i)
    {
        for (int j = 0; j < length2; ++j)
        {
            if (toupper(str1.at(i)) == toupper(str2.at(j))) {
                Array[i][j] = 1;
                if (i > 0 && j > 0) {
                    Array[i][j] += Array[i - 1][j - 1];
                }
                if (maxlength < Array[i][j]) {
                    Subsequence->push_back(toupper(str1.at(i)));
                    maxlength = Array[i][j];
                }

            }
            else {

                Array[i][j] = 0;
                if (i > 0) {
                    Array[i][j] = Array[i - 1][j];
                }
                if (Array[i][j] < Array[i][j - 1] &&j > 0 ) {
                    Array[i][j] = Array[i][j - 1];
                }
            }

        }
    }
    maxlength = Array[length1 - 1][length2 - 1];
    return maxlength;
}