I teoretisk datalogi , og især i tekstalgoritmer , er problemet med den korteste fælles efterfølgende et dobbelt problem med problemet med den længste almindelige efterfølgende . Vi finder også supersekvensanglisisme, men navnet konsekvens er mere logisk på fransk i modsætning til efterfølgelse.
Givet to sekvenser af symboler X og Y, en sekvens U er en on-sekvens fælles for X og Y , hvis X og Y er undersekvenser (eller suites ekstraherede) af U .
En kortere almindelig superstreng er en superstreng af mindste længde. Denne længde øges med summen af længden af de to sekvenser. For eksempel, hvis X = ab og Y = ba , er de to sekvenser U = aba og V = bab almindelige supersekvenser af X og Y af minimumslængden. Generelt, og som eksemplet viser, er en kortere fælles supersekvens ikke unik.
For to givne indgangssekvenser kan en kortere fælles undersekvens let beregnes ud fra en længere fælles sekvens. For eksempel for X = abcbdab og Y = bdcaba er den længste almindelige efterfølgende Z = bcba . Ved at indsætte symbolerne for X = a bcb d a b og Y = b d c a ba, som ikke vises i Z, mens vi opretholder rækkefølgen, får vi U = abdcabdab . Algoritmen viser også, at længden af en kortere fælles undersekvens er lig med summen af de to længder minus længden af den kortere fælles undersekvens: | U | = | X | + | Y | - | Z |.
Det mere generelle problem med at finde et symbol streng S for mindste længde, der er en superstreng af et sæt symbol strenge S 1 , S 2 , ..., S l , dvs. således at hver S i er en undersekvens af S, er NP -komplet. Der er i gennemsnit gode tilnærmelsesalgoritmer.