algorithm-最长公共子序列

题目描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad" ,顺次选1，3，5个字符就构成子串" cad" ,现给定两个字符串，求它们的最长共公子串。

输入

第一行两个字符串用空格分开。两个串的长度均小于2000 。

输出

最长子串的长度。

样例输入 Copy

abccd aecd

样例输出 Copy

3

#include<iostream>
using namespace std;
int main() {string a, b;int** c;cin >> a >> b;int m = a.length();int n = b.length();c = new int* [m+1];for (int i = 0; i <=m; i++) {c[i] = new int[n+1];}for (int i = 0; i < m + 1; i++) {for (int j = 0; j < n + 1; j++) {if (i == 0 || j == 0)c[i][j] = 0;else if (a[i - 1] == b[j - 1])//最后一个字母相同就加1c[i][j] = c[i - 1][j - 1] + 1;elsec[i][j] = max(c[i - 1][j], c[i][j - 1]);//如果最后一位字母不同就去除去这个最大的数}//表是从前向后填的}cout<< c[m][n];}