Största gemensamma delsträngen
Den längsta gemensamma delsträngen är en delsträng av två eller flera strängar som har den maximala längden.
Formellt är den största vanliga delsträngen av strängar strängen som uppfyller villkoret , operationen betyder att strängen är en (möjligen felaktig) delsträng av strängen .
Lösningen på problemet med att hitta den största gemensamma delsträngen för två strängar och , vars längder respektive , är att fylla tabellen med storleken enligt följande regel, förutsatt att tecknen i strängen är numrerade från en.
![\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}}\right.](https://wikimedia.org/api/rest_v1/media/math/render/svg/05bca60338f467057593742d7931efc78ad47b72)
Det maximala antalet i tabellen är längden på den längsta gemensamma delsträngen, själva delsträngen:
och .
![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)
Tabellen är fylld med värden för SUBSEQUENCE- och SUBEUENCS- raderna :
EFTERFÖLJNING 00000000000 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 000000 4 0 S 0 1 000000 1 0000000 _Få den största gemensamma UENC-delsträngen.
Komplexiteten hos en sådan algoritm är O (mn) .
Se även
- suffixträd
- Algoritmer på strängar
- Största vanliga följden
Anteckningar
| Strängar | |
|---|---|
| Stränglikhetsmått | |
| Sök efter delsträng | |
| palindromer | |
| Sekvensjustering | |
| Suffixstrukturer | |
| Övrig | |