Az elméleti számítástechnikában , és különösen a szöveges algoritmusokban , a legrövidebb közös részszakasz problémája a leghosszabb közös részszakasz problémájának kettős problémája . Találunk szuperkekvenciás angicizmust is, de a szekvencia név logikusabb a franciában, szemben a szekvenciával.
Ha két szekvencia adott szimbólumok X és Y, egy olyan szekvenciát U egy on-szekvenciát közös , hogy az X és Y , ha X és Y jelentése alszekvenciák (vagy lakosztályok extrahált) az U .
A rövidebb közös sztring egy minimális hosszúságú szuperhúr. Ezt a hosszúságot növeli a két szekvencia hosszának összege. Például, ha X = ab és Y = ba , akkor a két U = aba és V = bab szekvencia X és Y minimális hosszúságú közös szuper-következménye . Általánosságban, és ahogy a példa is mutatja, a rövidebb általános szubkekvencia nem egyedi.
Két megadott bemeneti szekvencia esetében egy rövidebb közös alszekvencia könnyen kiszámítható egy hosszabb közös alszekvenciából. Például X = abcbdab és Y = bdcaba esetében a leghosszabb közös alszekvencia Z = bcba . X = a bcb d a b és Y = b d c a ba szimbólumok beillesztésével, amelyek a sorrend megőrzése mellett nem jelennek meg Z-ben , U = abdcabdab-t kapunk . Az algoritmus azt is mutatja, hogy egy rövidebb közös alszekvencia hossza megegyezik a két hosszúság és a rövidebb közös alszegmens hosszának összegével: | U | = | X | + | Y | - | Z |.
Az általánosabb probléma egy minimális hosszúságú S szimbólum húr megtalálásával, amely az S 1 , S 2 , ..., S l szimbólum húrok halmazának a sztringje , vagyis olyan, hogy mindegyik S i S alszekvenciája , NP -teljes. Átlagosan vannak jó közelítő algoritmusok.