编辑代码

#include <iostream>
#include <string>
#include <set>
using namespace std;
int getLongestCommonSubstringSet(string wordA, string wordB, set<string> *subStringSet)
{
    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 curMaxLen = 0;
    //填充表格
    for (int i = 0; i < lengthA; ++i)
    {
        for (int j = 0; j < lengthB; ++j)
        {
            //字符串A的第i个字符和字符串B的第j个字符相等
            if (wordA.at(i) == wordB.at(j))
            {
                //记录下两个相等字符的长度1
                dpArray[i][j] = 1;
                //去掉相等字符，如果还有剩余子串，加上连续相等子串的长度
                if (i > 0 && j > 0)
                {
                    dpArray[i][j] += dpArray[i - 1][j - 1];
                }
                // 如果记录的最长公共子串长度小于当前的公共子串长度
                // 清理调记录的公共子串的集合，将当前的公共子串记到公共子串集合中
                if (curMaxLen < dpArray[i][j]) {
                    curMaxLen = dpArray[i][j];
                    subStringSet->clear();
                    subStringSet->insert(wordA.substr(i + 1 - curMaxLen, curMaxLen));
                }
                // 如果记录的最长公共子串长度等于当前的公共子串长度
                // 将当前公共子串加入到公共子串集合中
                else if (curMaxLen == dpArray[i][j]) {
                    subStringSet->insert(wordA.substr(i + 1 - curMaxLen, curMaxLen));
                }
            }
            // 连续的公共子串断开，长度记0
            else
            {
                dpArray[i][j] = 0;
            }
        }    
    }
    for (size_t i = 0; i < lengthA; i++)
    {
        delete dpArray[i];
    }
    delete [] dpArray;
    return curMaxLen;
}
int main() {
    string wordA = "";
    string wordB = "";
    while (true)
    {
        cout << "Please enter word A: " << endl;
        cin >> wordA;
        if (wordA == "0")
        {
            break;
        }
        cout << "Please enter word B: " << endl;
        cin >> wordB;
        set<string> longestCommonSubstringSet;
        int length = getLongestCommonSubstringSet(wordA, wordB, &longestCommonSubstringSet);
        cout << "The length of the longest common substring is " << length << endl;
        for (set<string>::iterator i = longestCommonSubstringSet.begin(); 
             i!=longestCommonSubstringSet.end(); ++i)
        {
            cout << *i << endl;
        }
    }
}