Jak znaleźć najdłuższy wspólny podciąg za pomocą drzew?
Najdłuższy wspólny problem związany z podciąganiem według wiki można rozwiązać za pomocą drzewa przyrostków.
Zwiki:
Najdłuższe wspólne podciągi zestawu łańcuchów można znaleźć, budując uogólnione drzewo przyrostków dla łańcuchów, a następnie znajdując najgłębsze wewnętrzne węzły, które mają węzły liści ze wszystkich łańcuchów w poddrzewie poniżej.
Nie rozumiem tego.
Przykład: jeśli mam:ABCDE
iXABCZ
wtedy drzewo przyrostków to (niektóre gałęzie zXABCZ
pominięty ze względu na miejsce):
Najdłuższy wspólny podciąg toABC
ale nie mogę nie zobaczyć, jak pomaga tutaj opis wiki.ABC
nie jest najgłębszym węzłem wewnętrznym z węzłami liści.
Jakaś pomoc, aby zrozumieć, jak to działa?