最大共通サブストリング(Longest Common Substring)

2473 ワード
substring
Longest Common SubstringとLongest Common Subsequenceには違いがあります
X =
Y =
XとYのLongest Common Sequenceは,長さ4
XとYのLongest Common Substringは長さは2
実はSubstring問題はSubsequence問題の特殊な状況で、2つの増加する下付きのシーケンスを探します
と使
xi1 == yj1
xi2 == yj2
......
xik == yjk
Subsequence問題とは異なり,Substring問題は下付きシーケンスがインクリメントされるだけでなく,毎回求められる.
増分の増分は1です.つまり、下付きの2つのシーケンスは次のとおりです.
および 
 
類比Subquence問題の動的計画解法,Substringも動的計画で解決することができる
c[i][j]は、X[i]とY[i]で終わる共通のサブストリングの長さを表し、X[i]がY[i]に等しくなければ、c[i][j]は0に等しく、例えば
X =
Y =
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
動的移行方程式は次のとおりです.
xi==yjの場合、c[i][j]=c[i-1][j-1]+1
もしxi!=yj,じゃあc[i][j]=0
 
最後にLongest Common Substringの長さが等しいことを求めます
max{c[i][j], 1<=i<=n, 1<=j<=m}
  
#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 250

int 	c[N][N];

void print_str(char *s1, char *s2, int i, int j)
{
	if (s1[i] == s2[j]) {
		print_str(s1, s2, i-1, j-1);
		putchar(s1[i]);
	}
}

int common_str(char *s1, char *s2)
{
	int		i, j, n, m, max_c;
	int		x, y;

	n = strlen(s1);
	m = strlen(s2);

	max_c = -1;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; 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_c) {
				max_c = c[i][j];
				x = i;
				y = j;
			}
			debug("c[%d][%d] = %d
", i, j, c[i][j]);
		}
	}

	print_str(s1, s2, x-1, y-1);
	printf("
");
	return max_c;
}

int main()
{
	char 	s1[N], s2[N];

	while (scanf("%s%s", s1, s2) != EOF) {
		debug("%s %s
", s1, s2);
		printf("%d
", common_str(s1, s2));
	}
	return 0;
}
 
goコンパイルエラーgo tool:no such tool compile
Linuxでparse-serverを立てる一連の流れ