题解 | #公共子串计算#C++动规标准（带图解示意）

最近一直在做各种动规 又做回来了 写个题解
举个例子 子串是dbc 公串是abcde
先初始化一个3行5列的数组record，初始化第0行和第0列

     a b c d e
d    0 0 0 1 0
b    0
c    0

相等的初始化为1，不相等的填充0就行了。之后从第1行第1列开始对比，如果相等，则当前位置的值为左上角的值+1，例如在对比第1行第1列时，b和b相等 则record[1][1] = 1

     a b c d e
d    0 0 0 1 0
b    0 1 0 0 0
c    0

到第2行时，c和c相等，则那个位置的值等于bb位置的值+1，则填充2

     a b c d e
d    0 0 0 1 0
b    0 1 0 0 0
c    0 0 2 0 0

填充好后，数组中最大值就是最大公共子串长度，c++代码如下
#include <iostream>
using namespace std;</iostream>

int main()
{
    string a,b;

    while(cin>>a>>b)
    {
        int record[a.size()][b.size()];
        int count = 0;
        for(int i=0;i<b.size();i++)
        {
            if(a[0] == b[i])
                record[0][i] = 1;
            else
                record[0][i] = 0;
        }
        for(int i=0;i<a.size();i++)
        {
            if(b[0] == a[i])
                record[i][0] = 1;
            else
                record[i][0] = 0;
        }

        for(int i=1;i<a.size();i++)
        {
            for(int j=1;j<b.size();j++)
            {
                if(a[i] == b[j])
                {
                    record[i][j] = record[i-1][j-1]+1;
                    if(record[i][j] > count)
                        count = record[i][j];
                }
                else
                {
                    record[i][j] = 0;
                }
            }
        }
        cout<<count<<endl;
    }
}