#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 999999

typedef struct dlobj {
	struct dlobj *prev;
	struct dlobj *next;
	int u;
	int c;
} dlobj;

typedef struct {
	dlobj *nil;
} dlist;

typedef struct {
	int n;
	int m;
	dlist **E;
} graph;

typedef struct {
	int priority;
	int value;
} heapdata; 

typedef struct {
	int max_size;
	int size;
	heapdata *A;
} heap;

dlobj *dlobj_new(int u, int c)
{
	dlobj *x;
	x = (dlobj*)malloc(sizeof(dlobj));
	x->u = u;
	x->c = c;
	return x;
}

dlist *dlist_new(void)
{
	dlist *L;
	L = (dlist*)malloc(sizeof(dlist));
	L->nil = malloc(sizeof(dlobj));
	L->nil->next = L->nil;
	L->nil->prev = L->nil;
	return L;
}

dlobj *dlist_search(dlist *L, int v)
{
	dlobj *x = L->nil->next;
	while (x != L->nil) {
		if (x->u == v) return x;
		x = x->next;
	}
	return NULL;
}


void dlist_append(dlist *L, dlobj *r)
{
	r->prev = L->nil->prev;
	r->next = L->nil;
  L->nil->prev->next = r;
	L->nil->prev = r;
}

graph *graph_new(int n) 
{
	int i,j;
	graph *G;
	G = (graph*)malloc(sizeof(graph));
	G->n = n;
	G->m = 0;
	G->E = malloc(n*sizeof(dlist*));
	for (i=1;i<=n;i++) {
		G->E[i-1] = dlist_new();
	}
	return G;
}

void graph_insert_edge(graph *G, int u, int v, int c) 
{
	dlobj *x;
	x = dlobj_new(v,c);
	dlist_append(G->E[u-1],x);
	G->m = G->m + 1;
}

dlobj *graph_firstedge(graph *G, int i)
{
	dlobj *r;
	r = G->E[i-1]->nil->next;
	if (r != G->E[i-1]->nil) return r;
	return NULL;
}

dlobj *graph_nextedge(graph *G, int i, dlobj *e)
{
	dlobj *r,*x; 
	x = dlist_search(G->E[i-1],e->u);
	if (x != NULL) r = x->next;
	if (r != G->E[i-1]->nil) return r;
  return NULL;
}

void heap_swap(heap *H, int i, int j)
{
	heapdata B;
	B = H->A[i];
	H->A[i] = H->A[j];
	H->A[j] = B;
}

void heapify(heap *H, int i)
{
	int l,r,smallest,size;
	heapdata *A;
	
	A = H->A; size = H->size;
	l = 2*i; r = 2*i+1;
	if (l <= size && A[l].priority < A[i].priority) smallest = l;
	else smallest = i;
	if (r <= size && A[r].priority < A[smallest].priority)
		smallest = r;
	if (smallest != i) {
		heap_swap(H,i,smallest);
		heapify(H,smallest);
	}
}

heap *heap_build(int n, heapdata *A, int max_size)
{
	int i;
	heap *H;
	H = (heap*)malloc(sizeof(heap));
	H->A = (heapdata*)malloc(sizeof(heapdata)*((max_size)+1));
	H->max_size = max_size;
	H->size = n;
	H->A = A;
	
	for (i=n/2;i>=1;i--) {
		heapify(H,i);
	}
	
	return H;
}

heapdata heap_extract_min(heap *H)
{
	heapdata B;
	B = H->A[1];
	heap_swap(H,1,H->size);
	H->size = (H->size)-1;
	heapify(H,1);
	return B;
}

void heap_insert(heap *H, heapdata x)
{
	heapdata *A;
	int i;
	A = H->A;
	H->size = H->size + 1;
	if (H->size > H->max_size) {
		printf("ERROR ?????????????????????????????????\n");
		exit(1);
	}
	i = H->size;
	A[i] = x;
	while (i>1 && A[i].priority < A[i/2].priority) {
		heap_swap(H,i,i/2);
		i = i/2;
	}
}

void heap_free(heap *H)
{
	free(H);
}

void Dijkstra(graph *G, int s, int *dist)
{
	int n,m,i,j;
	heap *H;
	heapdata *A,v,w;
	dlobj *edge;
	n = G->n; m = G->m;
	for (i=1;i<=n;i++) dist[i] = INFINITY;
	dist[s] = 0;
	
	A = malloc((m+1)*sizeof(heapdata));
	H = heap_build(0,A,m);
	
	v.value = s; v.priority = 0;
	heap_insert(H,v);
	
	while (H->size > 0) {
		v = heap_extract_min(H);
		if (v.value == n) break;
		if (dist[v.value] < v.priority) continue;
		
		edge = graph_firstedge(G,v.value);
		while (edge != NULL) {
			j = edge->u;
			if (dist[j] > dist[v.value]+edge->c) {
				dist[j] = dist[v.value]+edge->c;
				w.value = j; w.priority = dist[j];
				heap_insert(H,w);
			}
			edge = graph_nextedge(G,v.value,edge);
		}
	}
	free(A);
	heap_free(H);
}

int main(void) {
	int i,j,n,l,*dist;
	char buf1[1005],buf2[1005],*X,*Y;
	graph *G;
	
	if (scanf("%s %s",buf1,buf2) < 2) exit(1);
	n = strlen(buf1);
	l = strlen(buf2);
	X = malloc((n+1)*sizeof(char));
	Y = malloc((l+1)*sizeof(char));
	for (i=1;i<n+1;i++) X[i] = buf1[i-1];
	for (j=1;j<l+1;j++) Y[j] = buf2[j-1];
	X[0] = Y[0] = ' ';
	
	G = graph_new((n+1)*(l+1));
	
	
	for (i=0;i<n;i++) {
		for (j=0;j<l;j++) {
			if (X[i+1] == Y[j+1]) graph_insert_edge(G,i*(l+1)+j+1,(i+1)*(l+1)+j+2,0);
			else graph_insert_edge(G,i*(l+1)+j+1,(i+1)*(l+1)+j+2,1);
			graph_insert_edge(G,i*(l+1)+j+1,i*(l+1)+j+2,1);
			graph_insert_edge(G,i*(l+1)+j+1,(i+1)*(l+1)+j+1,1);
		}
		graph_insert_edge(G,i*(l+1)+l+1,(i+1)*(l+1)+l+1,1);
	}
	
	for (j=0;j<l;j++) graph_insert_edge(G,n*(l+1)+j+1,n*(l+1)+j+2,1);
	
	dist = malloc(((n+1)*(l+1)+1)*sizeof(double));
	Dijkstra(G,1,dist);
	printf("%d\n",dist[(n+1)*(l+1)]);
	
	return 0;

}