最長共通サブストリング問題

2つの文字列の最も長い共通のサブストリングを求めます:たとえば2つの文字列BDCABAとABCBDABを入力して、それらの最も長い共通のサブストリングはBDとABがあって、長さはすべて2です.
解法1:ダイナミックプランニング

#include <string>
#include <iostream>
using namespace std;

int longestCommonSubstring(string s1, string s2){
	int len1 = s1.size();
	int len2 = s2.size();
	int **c = new int*[len1 + 1];
	for(int i = 0; i < len1 + 1; ++i){
		c[i] = new int[len2 + 1];	
	}
	for(int i = 0; i < len1 + 1; ++i)
		c[i][0] = 0;
	for(int j = 0; j < len2 + 1; ++j)
		c[0][j] = 0;
	int max = -1;
	int x, y;
	for(int i = 1; i < len1 + 1; ++i){
		for(int j = 1; j < len2 + 1; ++j){
			if(s1[i - 1] == s2[j - 1])
				c[i][j] = c[i - 1][j - 1] + 1;
			else
				c[i][j] = 0;
			if(c[i][j] > max){
				max = c[i][j];
				x = i;
				y = j;
			}
		}
	}
	string s;
	int i = x - 1, j = y - 1;
	while(i >= 0 && j >= 0){
		if(s1[i] == s2[j]){
			s += s1[i];
			--i;
			--j;
		}
		else
			break;
	}
	reverse(s.begin(), s.end());
	cout << "        " << s << endl;
	for(int i = 0; i < len1 + 1; ++i)
		delete [] c[i];
	delete [] c;
	return max;
}

int main(){
	string s1, s2;
	cin >> s1 >> s2;
	int len = longestCommonSubstring(s1, s2);
	cout << "          ： " << len << endl;
	return 0;
}