Если у меня есть две строки одинаковой длины, A и B, которые имеют длину n и имеют самую длинную общую подпоследовательность (LCS (A, B)) длины (n - L), как я могу вычислить L в O((L + 1) n) время при использовании только O (L + 1) пробела?(Предполагая, что пространство, необходимое для хранения A и B, не учитывается).
Я пытался обратиться к исследовательским статьям, чтобы выяснить, как это сделать, но безрезультатно.Любая помощь в выяснении, как этого добиться, будет принята с благодарностью.Я знаю, что это возможно, потому что раньше у меня был исходный код, чтобы сделать это от третьей стороны, но теперь нужно переопределить его в другой среде.