Trova più piccola stringa contenente un dato insieme di lettere in una stringa più grande

Question

Diciamo che avete la seguente stringa:

FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNT 
LDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFY 
FFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQ 
XBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR 
AMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR 

Sto cercando di trovare la stringa più piccola contenente le lettere ABCDA.

Ho provato un approccio regex.

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

Questo funziona, ma trova solo stringhe in cui appaiono ABCDA (in questo ordine). Significa che non troverà sottostringhe in cui le lettere appaiono in un ordine come questo: BCDAA

Sto provando a cambiare la mia espressione regolare per tener conto di ciò. Come farei senza usare | e digitare tutti i diversi casi?

Answer 1

Non è possibile.

Consideriamo un caso speciale: supponiamo che le lettere che stai cercando siano A, A e B. Ad un certo punto nel tuo regexp ci sarà certamente un B. Tuttavia, le parti a sinistra e a destra di B sono indipendenti l'una dall'altra, quindi non è possibile fare riferimento da una all'altra. Il numero di A s corrisponde alla sottoespressione a destra di B dipende dal numero di A s già abbinato nella parte sinistra. Questo non è possibile con le espressioni regolari, quindi dovrai spiegare tutti i diversi ordini, che possono essere molti!

Un altro esempio popolare che illustra il problema consiste nell'abbinare le parentesi di apertura con le parentesi di chiusura. Non è possibile scrivere un'espressione regolare affermando che in una data stringa una sequenza di parentesi di apertura è seguita da una sequenza di parentesi di chiusura della stessa lunghezza. La ragione di ciò è che per contare le parentesi dovresti avere una macchina stack in contrasto con una macchina a stati finiti, ma le espressioni regolari sono limitate a pattern che possono essere abbinati usando le FSM.

Answer 2

Forse non è chiaro come utilizzare regex potrebbe essere (o meglio, per me espressione regolare non sono mai molto chiaro: D) è possibile usare la forza bruta (non così bruta)

creare un indice di punti "validi" del vostro stringa (quelli con le lettere che si desidera) e iterare con un doppio ciclo su di essa ottenendo sottostringhe contenenti almeno 5 di questi punti, verificando che siano valide soluzioni. Forse non il modo più efficiente, ma facile da implementare, da capire e probabilmente da ottimizzare.

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

Questo algoritmo non usa un'espressione regolare, ma ha trovato pure entrambe le soluzioni.

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);