参考来源：http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html

最长公共子串和最长公共子序列是典型的字符串问题，两者都有 O(m*n) 的动态规划解法，甚至前者还有 O(n) 的后缀自动机解法，但是原理过于复杂，参考来源中的文章给出了 O(1) 空间复杂度的最长公共子串解法，故本文采用之；最长公共子序列的动态规划解法是《算法导论》一书中的例子，如果只求长度而不需要重建最长公共子序列，空间复杂度为 O(n)，否则为 O(m*n)。

最长公共子串

参考来源中的文章有张解释地很好的图

这儿的矩阵是采用动态规划解法所得的矩阵，可以看到最长公共子串一定出现在某条对角线上，于是在外层循环只需要偏移一个字符串的头部，剩下部分再跟另一个字符串逐位比较看看在如此偏移下能找到最长的公共子串是多长，当外层循环偏移第一个字符串时（代码中的 A），对应图中指向左下角箭头的方向，当外层循环偏移第二个字符串时（代码中的 B），对应图中指向右上角箭头的方向，整个二维矩阵只遍历了一次，因此时间复杂度是 O(m*n)，只求长度代码如下：

/** http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html */
int longestCommonSubstring(std::string& A, std::string& B)
{
    if (A.empty() || B.empty())
        return 0;
    int longestLength = 0;
    int m = static_cast<int>(A.size()), n = static_cast<int>(B.size());
    for (int index = 0; index < 2; ++index) // shift A first, B second
    {
        int indices[2] = { 0, 0 };
        int &start = indices[index];
        int curSize = index == 0 ? m : n;
        for (start = index; start < curSize; ++start)
        {
            int i = indices[0], j = indices[1];
            // check to reduce some comparisons
            if (m - i <= longestLength || n - j <= longestLength)
                break;
            int length = 0;
            while (i < m && j < n)
            {
                if (A[i++] != B[j++])
                    length = 0;
                else if (longestLength < ++length)
                    longestLength = length;
            }
        }
    }
    return longestLength;
}

求所有不重复的最长公共子串的代码如下（注意 “longestLength <= ++length” 处取了等号，还有待比较串长度等于目前已知的最大长度时不能将之排除，否则可能错失某个最长公共子串）：

std::vector<std::string> longestCommonSubstring(std::string& A, std::string& B)
{
    std::vector<std::string> substrings;
    if (A.empty() || B.empty())
        return substrings;
    int longestLength = 0;
    int m = static_cast<int>(A.size()), n = static_cast<int>(B.size());
    std::vector<int> lengths(m < n ? m : n, 0);
    for (int index = 0; index < 2; ++index) // shift A first, B second
    {
        int indices[2] = { 0, 0 };
        int &start = indices[index];
        int curSize = index == 0 ? m : n;
        for (start = index; start < curSize; ++start)
        {
            int i = indices[0], j = indices[1];
            if (m - i < longestLength || n - j < longestLength) // check to reduce some more comparisons
                break;
            int length = 0;
            for (; i < m && j < n; ++i, ++j)
            {
                if (A[i] != B[j])
                    length = 0;
                else if (longestLength <= ++length)
                {
                    longestLength = length;
                    if (m < n)
                        lengths[i] = length;
                    else
                        lengths[j] = length;
                }
            }
        }
    }
    std::string &C = m < n ? A : B;
    size_t continousL = longestLength;
    for (size_t k = 0; k < lengths.size(); ++k)
    {
        if (lengths[k] == longestLength)
        {
            std::string sub = C.substr(k+1-continousL, continousL);
            size_t l = 0;
            for (; l < substrings.size(); ++l)
                if (sub == substrings[l])
                    break;
            if (l == substrings.size())
                substrings.push_back(sub);
        }
    }
    return substrings;
}

最长公共子序列

对于只需求最大长度的算法，不需要把整个二维矩阵都计算出来，因为每次在循环中计算当前行的时候只需用到前面那行，于是只需两行就够了，实现中可以交替地将其中一行作为当前行，另外一行作为前面那行

int longestCommonSubsequence(std::string& A, std::string& B)
{
    if (A.empty() || B.empty())
        return 0;
    int m = static_cast<int>(A.size()), n = static_cast<int>(B.size());
    std::vector<std::vector<int> > M(2, std::vector<int>(n+1, 0));
    int i = 1, j = 1, cur = 0, pre = 1;
    for (i = 1; i <= m; ++i)
    {
        pre = pre == 0 ? 1 : 0; // index for previous working row
        cur = cur == 0 ? 1 : 0; // index for current working row
        for (j = 1; j <= n; ++j)
        {
            if (A[i-1] == B[j-1])
                M[cur][j] = M[pre][j-1] + 1;
            else
                M[cur][j] = std::max(M[pre][j], M[cur][j-1]);
        }
    }
    return (m & 1) == 1 ? M[1][n] : M[0][n];
}

若要求出所有的最长公共子序列，文章 http://blog.csdn.net/u013074465/article/details/45392687 给出了一张解释地非常清晰的图，该例子就是《算法导论》中采用的例子

采用递归可以将这些路径全部找出，当 M[i-1][j] == M[i][j-1] 时，先调用 j-1 的递归函数，后调用 i-1 的递归函数，也就是先往左边走，后往上面走，这样最后得到的各最长公共子序列间的次序就是在原始字符串中越在前面位置的子序列就排在越前面

/** http://blog.csdn.net/u013074465/article/details/45392687 */
void LCSResult(std::vector<std::vector<int> >& M, int i, int j, std::string& A, std::string& B, std::string C, std::vector<std::string>& subsequences)
{
    while (i > 0 && j > 0)
    {
        if (A[i-1] == B[j-1])
        {
            C.push_back(A[--i]);
            --j;
        }
        else
        {
            if (M[i-1][j] > M[i][j-1])
                --i;
            else if (M[i-1][j] < M[i][j-1])
                --j;
            else
            {
                LCSResult(M, i, j-1, A, B, C, subsequences);
                LCSResult(M, i-1, j, A, B, C, subsequences);
                return;
            }
        }
    }
    std::reverse(C.begin(), C.end());
    size_t k = 0;
    for (; k < subsequences.size(); ++k)
        if (C == subsequences[k])
            break;
    if (k == subsequences.size())
        subsequences.push_back(C);
}

std::vector<std::string> longestCommonSubsequence(std::string& A, std::string& B)
{
    std::vector<std::string> subsequences;
    if (A.empty() || B.empty())
        return subsequences;
    int m = static_cast<int>(A.size()), n = static_cast<int>(B.size());
    std::vector<std::vector<int> > M(m+1, std::vector<int>(n+1, 0));
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (A[i-1] == B[j-1])
                M[i][j] = M[i-1][j-1] + 1;
            else
                M[i][j] = std::max(M[i-1][j], M[i][j-1]);
        }
    }
    LCSResult(M, m, n, A, B, "", subsequences);
    return subsequences;
}