Ilgiausias bendras posekis taikant dinaminį programavimą
Eilučių sufiksų A[i:],B[j:] ilgiausio bendro posekio ilgį pažymėkime L(i,j).
Esminės žinios
Eilučių sufiksų A[i:],B[j:] ilgiausio bendro posekio ilgį pažymėkime L(i,j). Tuščių sufiksų atveju gaunamas nulis; jei pirmieji simboliai sutampa, gaunama 1+L(i+1,j+1), kitu atveju – max(L(i+1,j),L(i,j+1)). Pildant lentelę indeksų mažėjimo tvarka, uždavinys išsprendžiamas per O((m+1)(n+1)) laiko ir naudojant tiek pat vietos lentelei; pagal pirmtakų pasirinkimus atkuriamas posekis.
Sąlygos ir taikymo ribos
- m,n yra eilučių ilgiai; simbolių lygybės patikros sąnaudos yra vienetinės.
- Posekio elementai neprivalo eiti iš eilės; tai skiriasi nuo ilgiausios bendros poeilutės.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Lecture16 LCS dalinis uždavinys, rekurentinis sąryšis, skaičiavimo tvarka, baziniai atvejai, atkūrimas ir sudėtingumas, spausdinti puslapiai 2–3.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-longest-common-subsequence
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra