Největší společný podřetězec
Nejdelší společný podřetězec je podřetězec dvou nebo více řetězců, který má maximální délku.
Formálně je největším společným podřetězcem řetězců řetězec , který splňuje podmínku , operace znamená, že řetězec je (možná nesprávným) podřetězcem řetězce .
Řešením problému najít největší společný podřetězec pro dva řetězce a , jejichž délky , resp., je vyplnit tabulku velikostí podle následujícího pravidla za předpokladu, že znaky v řetězci jsou číslovány od jedné.
![\left\{{\begin{array}{rclr}A_{{0j}}&=&0,&j=0\ldots n,\\A_{{i0}}&=&0,&i=0\ldots m,\ \A_{{ij}}&=&0,&s_{1}[i]\neq s_{2}[j],i\neq 0,j\neq 0,\\A_{{ij}}&=&A_{ {i-1j-1}}+1,&s_{1}[i]=s_{2}[j],i\neq 0,j\neq 0.\end{array}}\vpravo.](https://wikimedia.org/api/rest_v1/media/math/render/svg/05bca60338f467057593742d7931efc78ad47b72)
Maximální číslo v tabulce je délka nejdelšího společného podřetězce, samotného podřetězce:
a .
![s_{1}[u-A_{{uv}}+1]\ldots s_{1}[u]](https://wikimedia.org/api/rest_v1/media/math/render/svg/4968d6067c2747a45bdb66841720529f57bb7661)
![s_{2}[v-A_{{uv}}+1]\ldots s_{2}[v]](https://wikimedia.org/api/rest_v1/media/math/render/svg/3536560aa0e1a50b8a37d9823c0e41d037406272)
Tabulka je naplněna hodnotami pro řádky SUBSEQUENCE a SUBEUENCS :
SUBSEKVENCE 000000000000 S 0 1 00 1 0000000 U 00 2 0000 1 0000 B 000 3 00000000 E 00000 1 00 1 00 1 U 00 1 0000 1 0000 E 00000 1 00 2 00 1 N 0000000 3 00 00000000 4 0 S 0 1 0000000 1 0000000 _Získejte největší společný podřetězec UENC.
Složitost takového algoritmu je O (mn) .
Viz také
- příponový strom
- Algoritmy na řetězcích
- Největší společná podsekvence
Poznámky
| Struny | |
|---|---|
| Míry podobnosti řetězců | |
| Hledání podřetězců | |
| palindromy | |
| Sekvenční zarovnání | |
| Struktury přípon | |
| jiný | |