Матч 298, Подсчет общих подпоследовательностей (CountingCommonSubsequences)

Дивизион 1, Уровень 3

Подпоследовательность образуется из строки удалением нуля или нескольких символов из нее. По заданным трем строкам следует подсчитать количество их разных непустых общих подпоследовательностей.

Класс: CountingCommonSubsequences

Метод: long long countCommonSubsequences(String a,

String b, String c)

Ограничения: a, b и c содержат от 1 до 50 символов ‘a’ – ‘z’.

Вход. Три строки a, b и c.

Выход. Количество общих подпоследовательностей трех строк a, b и c.

Пример входа

a	b	c
“call”	“accelerate”	“candle”
“topcoder”	“topcoder”	“topcoder”
“no”	“correct”	“answer”

Пример выхода

6

239

0

РЕШЕНИЕ

динамическое программирование

В ячейке f[i][j][k] будем хранить количество общих подпоследовательностей строк a₁a₂…a_i, b₁b₂…b_j и c₁c₂…c_k., где a_i = b_j = c_k. Если для тройки (i, j, k) последнее равенство не выполняется, то полагаем f[i][j][k] = 0. Если i = 0, то считаем, что строка a пустая. Аналогично при j = 0 (k = 0) считаем, что строка b (c) пустая. Положим f[0][0][0] = 1, считая, что общей подпоследовательностью трех пустых строк является пустая строка.

Искомое количество общих подпоследовательностей трех строк a, b и c равно

или – 1

где l, m, n – длины соответственно строк a, b и c.

Вычисление значений f[i][j][k] совершаем следующим образом. Перебираем все возможные значения троек (i, j, k) и для каждого значения f[i][j][k], большего нуля (a_i = b_j = c_k) перебираем все буквы латинского алфавита и для каждой буквы ищем ее появление во всех строках в позициях, больших соответственно i, j и k. Пусть такими позициями будут x, y и z. Добавляем к f[x+1][y+1][z+1] значение f[i][j][k] (индексы сдвинуты на 1, так как нумерация массивов в Си начинается с нуля, а индексу 0 в массиве f соответствует пустая строка).

ПРИМЕР

Пусть a = b = c = “abc”. Тогда

f[0][0][0] = 1, общая подпоследовательность (“”, “”, “”).

f[1][1][1] = 1, общая подпоследовательность (“a”, “a”, “a”).

f[2][2][2] = 2, общие подпоследовательности (“b”, “b”, “b”), (“ab”, “ab”, “ab”).

f[3][3][3] = 4, общие подпоследовательности (“c”, “c”, “c”), (“bc”, “bc”, “bc”),

(“ac”, “ac”, “ac”), (“abc”, “abc”, “abc”).

Остальные значения f[i][j][k] равны нулю.

Количество общих подпоследовательностей равно 1 + 2 + 4 = 7.

ПРОГРАММА

#include <cstdio>

#include <string>

using namespace std;

long long f[51][51][51], res;

class CountingCommonSubsequences

{

public:

long long countCommonSubsequences(string a, string b, string c)

{

int i, j, k, x, y, z;

f[0][0][0] = 1; res = 0;

for(i = 0; i <= a.size(); i++)

for(j = 0; j <= b.size(); j++)

for(k = 0; k <= c.size(); k++)

if (f[i][j][k] > 0)

{

for(char ch = 'a'; ch <= 'z';ch++)

{

x = a.find(ch,i); y = b.find(ch,j); z = c.find(ch,k);

if (x != string::npos && y != string::npos && z != string::npos)

f[x+1][y+1][z+1] += f[i][j][k];

}

res += f[i][j][k];

}

return res - 1;

}

};