编辑代码

#include <iostream>
#include <string>

using namespace std;

int getLongestCommonSequence(string wordA, string wordB, string *sequence) {
   
    int lengthA = wordA.length();
    int lengthB = wordB.length();

    if (0 == lengthA || 0 == lengthB) {
        cout << "Please check word you entered." << endl;
        return -1;
    }

    // 创建表格，横轴是字符串A，纵轴是字符串B
    int **dpArray = new int*[lengthA];
    for (int i = 0; i < lengthA; ++i) {
        dpArray[i] = new int[lengthB];
    }

    int maxLength = 0;

    // 填充表格
    for (int i = 0; i < lengthA; ++i)
    {
        for (int j = 0; j < lengthB; ++j)
        {
            // 字符串A的i位置的字符和字符串B的j位置的字符相等
            if (toupper(wordA.at(i)) == toupper(wordB.at(j))) {
                // 记录下相等的公共子序列长度为1
                dpArray[i][j] = 1;
                // 如果去掉相等的字符后，还有剩余的子串，加上子串的最长公共子序列
                if (i > 0 && j > 0) {
                    dpArray[i][j] += dpArray[i - 1][j - 1];
                }
                if (maxLength < dpArray[i][j]){
                    sequence->push_back(toupper(wordA.at(i)));
                    maxLength = dpArray[i][j];
                }
         
            }
            else {
                // 字符串A的i位置的字符和字符串B的j位置的字符不相等
                dpArray[i][j] = 0;
                // 如果去掉字符串A的i位置的字符，字符串A还有子串，记录下剩下的字符串A子串与字符串B的子串的最长公共子序列长度
                if (i > 0) {
                    dpArray[i][j] = dpArray[i - 1][j];
                }

                // 如果去掉字符串B的j位置的字符，字符B还有子串，比较剩下的字符串B子串与字符串A的子串的最长公共子序列长度
                // 与之前去掉字符串A的i位置的字符后的最长公共子序列长度，选取较大的最大公共子序列长度
                if (j > 0 && dpArray[i][j] < dpArray[i][j - 1]) {
                    dpArray[i][j] = dpArray[i][j - 1];
                }
            }

        }    
    }

    // 表格的最后一格就是字符串A和字符串B的最长公共子序列的长度
    maxLength = dpArray[lengthA - 1][lengthB - 1];
    for (size_t i = 0; i < lengthA; i++)
    {
        delete dpArray[i];
    }

    delete [] dpArray;
    
    return maxLength;
}



int main() {
    string wordA = "MIGRATION";
    string wordB = "Migrapion";

    string longestCommonSequence = "";

    int length = getLongestCommonSequence(wordA, wordB, &longestCommonSequence);

    cout << "The length of the longest common sequence is " << length << endl;
    cout << longestCommonSequence << endl; 


    wordA = "Fish";
    wordB = "Hist";

    longestCommonSequence = "";

    length = getLongestCommonSequence(wordA, wordB, &longestCommonSequence);

    cout << "The length of the longest common sequence is " << length << endl;
    cout << longestCommonSequence << endl; 
}