Я реализую проблему самой длинной общей подпоследовательности в C #.Мне нужно обнаружить ВСЕ общие максимальные подпоследовательности между двумя строками.
Для этого я создаю таблицу, используя алгоритм Нидлмана-Вунша , чтобы сохранить последовательность LCS длякаждый шаг расчета.
Есть ли шанс определить, сколько было найдено максимальных подпоследовательностей (с использованием таблицы)?
В зависимости от этого я хочу выбратьметод, как собрать каждую подпоследовательность.Дело в том, что для одна подпоследовательность рекурсия не требуется, поэтому она даст лучшую производительность .И это очень важно для моей задачи.
Вот фрагмент кода, в котором реализованы основные функции проекта:
private static int[][] GetMatrixLCS(string x, string y)
{
var lenX = x.Length;
var lenY = y.Length;
matrixLCS = new int[lenX + 1][];
for (var i = 0; i < matrixLCS.Length; i++)
{
matrixLCS[i] = new int[lenY + 1];
}
for (int i = 0; i <= lenX; i++)
{
for (int j = 0; j <= lenY; j++)
{
if (i == 0 || j == 0)
matrixLCS[i][j] = 0;
else
if (x[i - 1] == y[j - 1])
matrixLCS[i][j] = matrixLCS[i - 1][j - 1] + 1;
else
matrixLCS[i][j] = Math.Max(matrixLCS[i - 1][j], matrixLCS[i][j - 1]);
}
}
return matrixLCS;
}
static HashSet<string> FindAllLcs(string X, string Y, int lenX, int lenY)
{
var set = new HashSet<string>();
if (lenX == 0 || lenY == 0)
return emptySet;
if (X[lenX - 1] == Y[lenY - 1])
{
var tempResult = FindAllLcs(X, Y, lenX - 1, lenY - 1);
foreach (var temp in tempResult)
set.Add(temp + X[lenX - 1]);
return set;
}
if (matrixLCS[lenX - 1][lenY] >= matrixLCS[lenX][lenY - 1])
set = FindAllLcs(X, Y, lenX - 1, lenY);
if (matrixLCS[lenX][lenY - 1] >= matrixLCS[lenX - 1][lenY])
set.UnionWith(FindAllLcs(X, Y, lenX, lenY - 1));
return set;
}
И пример с двумя типами входов и ожидаемыми выходами:
public void SingleOutput()
{
var sequence = LCS.FindLCS("ABC", "AB");
Assert.AreEqual(1, sequence.Length);
Assert.AreEqual("AB", sequence[0]);
}
public void MultipleOutput()
{
var sequence = LCS.FindLCS("BCAB", "ABC");
Assert.AreEqual(2, sequence.Length);
Assert.AreEqual("AB", sequence [0]);
Assert.AreEqual("BC", sequence [1]);
}
Любая помощь будет принята с благодарностью.