Listing 1516

#include <stdio.h>
#include <memory.h>
#define MN 1001
int n, m;
char a[MN], b[MN];
void input()
{
	scanf("%s%s", &a[1], &b[1]);
	n = strlen(&a[1]); m = strlen(&b[1]);
}
int w1[MN][MN], w2[MN][MN], c[MN][MN];
int C(int i, int j)
{
	if (i < 0 || j < 0) return -1;
	if (c[i][j] >= 0) return c[i][j];
	int &v = c[i][j], p;
	
	if (C(i,j-1) >= 0) {
		if (v > C(i,j-1)+1 || v < 0)
			v = C(i,j-1)+1;
	}
	if (C(i-1,j) >= 0) {
		if (v > C(i-1,j)+1 || v < 0)
			v = C(i-1,j)+1;
	}
	if (C(i-1,j-1) >= 0) {
		if (v > C(i-1,j-1)+(a[i]!=b[j]) || v < 0)
			v = C(i-1,j-1)+(a[i]!=b[j]);
	}
	if (i-1 >= 0) {
		p = w1[j][i-1];
		if (C(p-1,j-2) >= 0) {
			if (a[i] == b[j-1]) {
				if (v > C(p-1,j-2)+(i-p) || v < 0)
					v = C(p-1,j-2)+(i-p);
			}
		}
	}
	if (j-1 >= 0) {
		p = w2[i][j-1];
		if (C(i-2,p-1) >= 0) {
			if (a[i-1] == b[j]) {
				if (v > C(i-2,p-1)+(j-p) || v < 0)
					v = C(i-2,p-1)+(j-p);
			}
		}
	}
	return v;
}
void process()
{
	int i, j;
	
	for (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			if (a[j] == b[i])
				w1[i][j] = j;
			else w1[i][j] = w1[i][j-1];
		} 
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (a[i] == b[j])
				w2[i][j] = j;
			else
				w2[i][j] = w2[i][j-1];
		}
	}
	memset(c,128,sizeof(c));
	c[0][0] = 0;
	printf("%d\n", C(n,m));
}
int main()
{
	freopen("input.txt", "r", stdin);
	input();
	process();
	return 0;
}