Znajdź najmniejszą podciąg zawierający dany zestaw liter w większym ciągiem

Question

że masz następujący ciąg:

FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNT 
LDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFY 
FFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQ 
XBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR 
AMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR 

Próbuję znaleźć najmniejszą podciąg zawierający litery ABCDA.

Próbowałem podejście regex.

console.log(str.match(/[A].*?[B].*?[C].*?[D].*?[A]/gm).sort((a, b) => a.length - b.length)[0]); 

Działa, ale znajduje tylko ciągi, w których pojawia się ABCDA (w tej kolejności). To znaczy, że nie znajdzie podciągów, w których litery pojawiają się w następującej kolejności: BCDAA

Próbuję zmienić moje wyrażenie regularne, aby uwzględnić to. Jak to zrobić, bez korzystania z | i wypisać wszystkie różne przypadki?

Answer 1

Nie możesz.

Rozważmy specjalny przypadek: załóżmy, że szukane litery to: A, A i B. W pewnym momencie twojego regexp z pewnością będzie B. Jednak części po lewej i po prawej stronie są niezależne od siebie, więc nie można odwoływać się od jednego do drugiego. Liczba A s dopasowanych w podwyrażeniu na prawo od B zależy od liczby dopasowanych A s w lewej części. Nie jest to możliwe w przypadku wyrażeń regularnych, więc będziesz musiał rozłożyć wszystkie rozkazy, które mogą być liczne!

Innym popularnym przykładem ilustrującym problem jest dopasowanie nawiasów otwierających do nawiasów zamykających. Nie można zapisać wyrażenia regularnego, potwierdzając, że w danym ciągu po sekwencji nawiasów otwiera się sekwencja nawiasów zamykających o tej samej długości. Powodem tego jest to, że w celu zliczenia nawiasów potrzebna jest maszyna stosu, w przeciwieństwie do skończonej maszyny stanów, ale wyrażenia regularne są ograniczone do wzorców, które można dopasować za pomocą FSM.

Answer 2

Może nie tak oczywiste, jak przy użyciu regex może być (dobrze, dla mnie regex nigdy nie są bardzo jasne: D) można użyć brutalnej siły (nie tak brutalnej)

Utwórz indeks „poprawnych” punktów z twoich string (te z literami, które chcesz) i iteruj za pomocą podwójnej pętli nad ciągiem znaków zawierających co najmniej 5 punktów, sprawdzając, czy są to poprawne rozwiązania. Może nie jest to najbardziej efektywny sposób, ale łatwy do wdrożenia, zrozumienia i prawdopodobnie optymalizacji.

var haystack="UGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNTLDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFYFFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQXBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR"; 
 
var needle="ABCD"; 
 
var size=haystack.length; 
 
var candidate_substring=""; 
 
var minimal_length=size; 
 
var solutions=new Array(); 
 
var points=Array(); 
 
for(var i=0;i<size;i++){ 
 
\t if(needle.indexOf(haystack[i])>-1) points.push(i); 
 
} 
 
var limit_i= points.length-4; 
 
var limit_k= points.length; 
 
for (var i=0;i<limit_i;i++){ 
 
    for(var k=i;k<limit_k;k++){ 
 
\t if(points[k]-points[i]+1<=minimal_length){ 
 
\t \t candidate_substring=haystack.substr(points[i],points[k]-points[i]+1); 
 
\t \t if(is_valid(candidate_substring)){ 
 
\t \t solutions.push(candidate_substring); 
 
\t \t if(candidate_substring.length < minimal_length) minimal_length=candidate_substring.length; 
 
\t \t } 
 
\t } 
 
    } 
 
} 
 
document.write('<p>Solution length:'+minimal_length+'<p>'); 
 
for(var i=0;i<solutions.length;i++){ 
 
    if(solutions[i].length<=minimal_length) document.write('<p>Solution:'+solutions[i]+'<p>'); 
 
} 
 

 
function is_valid(candidate_substring){ 
 
    //verify we've got all characters 
 
    for(var j=0;j<candidate_substring.length;j++){ 
 
    if(candidate_substring.indexOf(needle.charAt(j))<0) return false; 
 
    } 
 
    //...and verify we have two "A" 
 
    if(candidate_substring.indexOf("A")==candidate_substring.lastIndexOf("A")) return false; 
 
    return true; 
 
}

Answer 3

Algorytm ten nie korzysta z regex, ale uważamy, że zarówno rozwiązania, jak również.

var haystack = 'FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNTLDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFYFFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQXBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGRAMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR'; 
var needle = 'ABCDA'; // the order of letters doesn't matter 

var letters = {}; 
needle.split('').forEach(function(ch) { 
    letters[ch] = letters[ch] || 0; 
    letters[ch]++; 
}); 

var shortestSubstringLength = haystack.length; 
var shortestSubstrings = []; // storage for found substrings 

var startingPos = 0; 
var length; 
var currentPos; 
var notFound; 
var letterKeys = Object.keys(letters); // unique leters 
do { 
    lettersLeft = JSON.parse(JSON.stringify(letters)); // copy letters count object 
    notFound = false; 
    posStart = haystack.length; 
    posEnd = 0; 
    letterKeys.forEach(function(ch) { 
    currentPos = startingPos; 
    while (!notFound && lettersLeft[ch] > 0) { 
     currentPos = haystack.indexOf(ch, currentPos); 
     if (currentPos >= 0) { 
     lettersLeft[ch]--; 
     posStart = Math.min(currentPos, posStart); 
     posEnd = Math.max(currentPos, posEnd); 
     currentPos++; 
     } else { 
     notFound = true; 
     } 
    } 
    }); 
    if (!notFound) { 
    length = posEnd - posStart + 1; 
    startingPos = posStart + 1; // starting position for next iteration 
    } 
    if (!notFound && length === shortestSubstringLength) { 
    shortestSubstrings.push(haystack.substr(posStart, length)); 
    } 
    if (!notFound && length < shortestSubstringLength) { 
    shortestSubstrings = [haystack.substr(posStart, length)]; 
    shortestSubstringLength = length; 
    } 
} while (!notFound); 

console.log(shortestSubstrings);