Пример. Пусть X = abcdgh, Y = aedfhr. Наибольшей общей подпоследовательностью будет adh, ее длина равна f(6, 6) = 3

Пример. Пусть X = abcdgh, Y = aedfhr. Наибольшей общей подпоследовательностью будет adh, ее длина равна f(6, 6) = 3.

c		X	a	b	c	d	g	h
		0	1	2	3	4	5	6
Y	0	0	0	0	0	0	0	0
a	1	0	1 (a)	1	1	1	1	1
e	2	0	1	1	1	1	1	1
d	3	0	1	1	1	2 (d)	2	2
f	4	0	1	1	1	2	2	2
h	5	0	1	1	1	2	2	3 (h)
r	6	0	1	1	1	2	2	3

{

return (i > j) ? i : j;

int m[2][1001];

int lenx, leny;
Входные данные обрабатываем, пока не встретится конец файла. Читаем две входные последовательности в массивы x и y. При этом значения x[0] и y[0] обнуляем, а входные строки заносим в массивы, начиная с первой ячейки. Длины последовательностей сохраняем в переменных lenx и leny.
x[0] = y[0] = 0;

while(gets(x+1),gets(y+1))

{

lenx = strlen(x+1); leny = strlen(y+1);

for(i = 1; i <= lenx; i++)

for(j = 1; j <= leny; j++)

if (x[i] == y[j]) m[i % 2][j] = 1 + m[(i-1)%2][j-1];

else m[i % 2][j] = max(m[(i-1)%2][j],m[i%2][j-1]);
В конце алгоритма длина наибольшей общей подпоследовательности будет находиться в ячейке m[lenx%2][leny]. Выводим ее.
printf("%d\n",m[lenx%2][leny]);

}
6. Путешествие Теобальдо [Вальядолид, 10681]. Пусть go^k[i] = 1, если Теобальдо может попасть из начального города s в город i за k переходов, иначе go^k[i] = 0. Изначально go⁰[s] = 1, go⁰[i] = 0, 1  i  c, i s. Будем моделировать все возможные переходы Теобальдо, вычисляя значения go^k[i], 1  i  c, 1  k  d. Очевидно, что go^k[i] = 1, если существует такое j, что go^k-1[j] = 1 и существует ребро из города j в город i. Имея все значения go^k[i] (1  i  c) для некоторого k (0  k  d – 1), вычисляем все значения go^k+1[i], 1  i  c. Теобальдо может совершить переход из города s в город e за d дней, если go^d[e] = 1.