第8回ブルーブリッジカップ省試合C++B組最大共通サブストリング

見出し:最大共通サブストリング
最大共通サブストリング長の問題は、2つのストリングのすべてのサブストリングの中で一致できる最大長を求めることです.
例えば、「abcdkkk」と「baabcdabc」では、最も長い共通サブストリングが「abcd」であるため、最大共通サブストリング長は4である.
次のプログラムはマトリクス法を用いて解くが,これは列の規模が大きくない場合に有効な解法である.
この解法の考え方を分析し,スクライブ部分で欠落したコードを補完してください.

#include 
#include 

#define N 256
int f(const char* s1, const char* s2)
{
	int a[N][N];
	int len1 = strlen(s1);
	int len2 = strlen(s2);
	int i,j;
	
	memset(a,0,sizeof(int)*N*N);
	int max = 0;
	for(i=1; i<=len1; i++){
		for(j=1; j<=len2; j++){
			if(s1[i-1]==s2[j-1]) {
				a[i][j] = __________________________;  //  
				if(a[i][j] > max) max = a[i][j];
			}
		}
	}
	
	return max;
}

int main()
{
	printf("%d
", f("abcdkkk", "baabcdadabc"));
	return 0;
}

注意:欠落したコードのみをコミットし、既存のコードと記号をコミットしないでください.説明文も提出しないでください.
 
答え:a[i-1][j-1]+1
考え方:テーマを見ると板の問題であることがわかります.このアルゴリズムを知っている人はすぐに記入することができます.しかし、当時の試合の時、私はこれが何なのか全然知らなかった.理解して出したのだ.a[i][j]は、s 1列の前のi文字とs 2列の前のj文字がそれぞれ最後の文字を含む最大共通サブ列長、動的計画問題を表す.