Cacher is the code snippet organizer for pro developers

思路

1. 把两个字符串分别以行和列组成一个二维矩阵。
2. 比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3. 通过查找出值为 1 的最长对角线就能找到最长公共子串。
4. 通过记录终点序号，加上长度则可以获取公共子串。

状态转移方程：

f[i][j] = 1 + f[i - 1][j - 1]

代码

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string str1, str2;
    while(cin >> str1 >> str2)
    {
        int row = str1.size();
        int cloumn = str2.size();
        if (row == 0 || cloumn == 0)
        {
            cout << endl;
            continue;
        }
        
        int** record = new int*[row];
        for (int i = 0; i < row; ++i)
        {
            record[i] = new int[cloumn];
            record[i][0] = str1[i] == str2[0] ? 1 : 0;
        }
        for (int i = 0; i < cloumn; ++i)
        {
            record[0][i] = str2[i] == str1[0] ? 1 : 0;
        }
        
        int max = 0;
        int maxEnd = 0;
        int type = row > cloumn? 0 : 1; // 0 -> 2 1 -> 1
        for (int i = 1; i < row; ++i)
        {
            for (int j = 1; j < cloumn; ++j)
            {
                if (str1[i] == str2[j])
                {
                    record[i][j] = 1 + record[i-1][j-1];
                    if (max < record[i][j])
                    {
                        max = record[i][j];
                        maxEnd = type ? i : j;
                    }
                    else if (max == record[i][j])
                    {
                        int end = type ? i : j;
                        maxEnd = end < maxEnd ? end : maxEnd;
                    }
                }
                else
                {
                    record[i][j] = 0;
                }
            }
        }
        
        if (type)
        {
            cout << str1.substr(maxEnd - max + 1, max) << endl;
        }
        else
        {
            cout << str2.substr(maxEnd - max + 1, max) << endl;
        }
    }
}