I teoretisk informatikk , og spesielt i tekstalgoritmikk , er problemet med den korteste vanlige undersekvensen et dobbelt problem med problemet med den lengste vanlige undersekvensen . Vi finner også supersekvensanglisisme, men navnet konsekvens er mer logisk på fransk i motsetning til konsekvens.
Gitt to sekvenser av symboler X og Y, en sekvens U er en på-sekvens felles for X og Y hvis X og Y er undersekvenser (eller Suite ekstraherte) av U .
En kortere vanlig superstreng er en superstreng av minimum lengde. Denne lengden økes med summen av lengden på de to sekvensene. For eksempel, hvis X = ab og Y = ba , er de to sekvensene U = aba og V = bab vanlige supersekvenser av X og Y av minimumslengde. Generelt, og som eksemplet viser, er en kortere vanlig supersekvens ikke unik.
For to gitte inngangssekvenser kan en kortere felles undersekvens enkelt beregnes fra en lengre felles undersekvens. For eksempel, for X = abcbdab og Y = bdcaba , er den lengste vanlige følgen Z = bcba . Ved å sette inn symbolene på X = a bcb d a b og Y = b d c a ba som ikke vises i Z mens vi bevarer rekkefølgen, får vi U = abdcabdab . Algoritmen viser også at lengden på en kortere felles undersekvens er lik summen av de to lengdene minus lengden på den kortere felles undersekvensen: | U | = | X | + | Y | - | Z |.
Det mer generelle problemet med å finne en symbolstreng S av minimumslengde som er en overstreng av et sett med symbolstrenger S 1 , S 2 , ..., S l , dvs. slik at hver S i er en undersekvens av S, er NP -fullstendig. Det er gode tilnærmelsesalgoritmer i gjennomsnitt.