最长公共字串

找出X={x1,x2,x,3,x4,x5…….} Y={y1,y2,y3,y4……}最长公共字串
由最优子结构性质可建立递归关系如下：

#include<iostream>
using namespace std;
void LSCLengh(int m, int n, char x[], char y[]) {
    //m是x数组长度
    //n是y数组长度
    //c[m+1][n+1]数组是辅助空间，记录
    int c[7 + 1][6 + 1];//辅助空间
    int i, j;
    int p=0;//记录公共子串末尾位置,如果要输出公共字串：（Xp-len+1,Xpmax)
    int len=0;//记录公共字串长度
    for (i = 0; i <= m; i++)
        c[i][0] = 0;
    for (i = 1; i <= n; i++)
        c[0][i] = 0;//边缘初始化
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++)
        {
            if (x[i - 1] == y[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                if (c[i][j] > len) {
                    len = c[i][j];
                    p = i;
                }
            }
            else{
                c[i][j] = 0;
            }
        }
    }
    cout << endl;
    for (i = 0; i <= m; i++) {
        cout << " ";
        for (j = 0; j <= n; j++)
            cout << c[i][j] << " ";
        cout << endl;
    }
    cout << "  公共子串末尾位置:p=" << p << endl;
    cout << "  公共字串长度:len=" << len << endl << "  公共字串为：";
    for (i = p - len + 1; i <= p; i++)
        cout << x[i-1];
    cout << endl;
}
int main() {
    char x[] = { 'A','B','C','A','D','B','B' };
    char y[] = { 'B','C','E','D','B','B' };
    LSCLengh(7, 6, x, y);
    return 0;
}

运行结果：