Cel mai mare subșir comun

Cel mai lung subșir comun este un subșir de două sau mai multe șiruri care are lungimea maximă.

Formal, cel mai mare subșir comun de șiruri este șirul care îndeplinește condiția , operația înseamnă că șirul este un subșir (posibil impropriu) al șirului . $s_{1},s_{2},\ldots s_{n}$ $\left.w^{*}\right.$ $\|w^{*}\|=\max(\{\|w\||w\sqsubseteq s_{i},i=1,\ldots n\})$ $w\sqsubseteq s_{i}$ $\left.w\right.$ $\left.s_{i}\dreapta.$

Soluția problemei găsirii celui mai mare subșir comun pentru două șiruri și , ale căror lungimi și respectiv, este de a umple tabelul cu dimensiunea conform următoarei reguli, presupunând că caracterele din șir sunt numerotate de la unu. $\left.s_{1}\dreapta.$ $\left.s_{2}\dreapta.$ $\left.m\dreapta.$ $\left.n\dreapta.$ $\left.A_{{ij}}\right.$ $(m+1)\ori (n+1)$

$\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.$

Numărul maxim din tabel este lungimea celui mai lung subșir comun, subșirul în sine: $\left.A_{{uv}}\dreapta.$

$s_{1}[u-A_{{uv}}+1]\ldots s_{1}[u]$ și . $s_{2}[v-A_{{uv}}+1]\ldots s_{2}[v]$

Tabelul este completat cu valori pentru rândurile SUBSEQUENCE și SUBEUENCS :

SUBSECVENȚA 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 _

Obțineți cel mai mare subșir comun UENC.

Complexitatea unui astfel de algoritm este O (mn) .

Vezi și

Note

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun