Найти наименьшее подстроку, содержащую заданный набор букв в большей строки

Question

Say вы имеете следующую строку:

FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNT 
LDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFY 
FFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQ 
XBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR 
AMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR 

Я пытаюсь найти наименьшее подстроку, содержащую буквы ABCDA.

Я пробовал подход с регулярным выражением.

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

Это работает, но он находит только строки, где появляется ABCDA (в указанном порядке). Это означает, что он не найдет подстроку, где буквы появятся в следующем порядке: BCDAA

Я пытаюсь изменить свое регулярное выражение для объяснения этого. Как мне это сделать без использования | и напечатать все разные случаи?

Answer 1

Вы не можете.

Давайте рассмотрим специальный случай: предположим, что вы ищете A, A и B. В какой-то момент в вашем регулярном выражении обязательно будет B. Однако части слева и справа от B не зависят друг от друга, поэтому вы не можете ссылаться друг на друга. Количество A s соответствует подвыражению справа от B, зависит от количества совпадений A s в левой части. Это невозможно с регулярными выражениями, поэтому вам придется развернуть все разные заказы, которых может быть много!

Другим популярным примером, иллюстрирующим проблему, является совмещение открывающих скобок с закрывающими скобами. Невозможно написать регулярное выражение, утверждающее, что в данной строке последовательность открывающих скобок сопровождается последовательностью замыкающих скобок одинаковой длины. Причиной этого является то, что для подсчета скобок вам понадобится машина стека в отличие от конечного конечного автомата, но регулярные выражения ограничены шаблонами, которые могут быть сопоставлены с использованием FSM.

Answer 2

Может быть, не ясно, как с помощью регулярных выражений может быть (ну, для меня регулярное выражение никогда не совсем ясно: D), вы можете использовать грубую силу (не так перебор)

Создать индекс «действительных» точек вашего string (те, у кого есть буквы), и итерации с двойным циклом, получая подстроки, содержащие по крайней мере 5 из этих точек, проверяя, что они являются действительными решениями. Возможно, это не самый эффективный способ, но его легко реализовать, понять и, возможно, оптимизировать.

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

Этот алгоритм не использует регулярное выражение, но нашел оба решения, а также.

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