kleinste Teilkette findet einen bestimmten Satz von Buchstaben in einem größeren String

Question

Angenommen, Sie haben die folgende Zeichenfolge enthält:

FJKAUNOJDCUTCRHBYDLXKEODVBWTYPTSHASQQFCPRMLDXIJMYPVOHBDUGSMBLMVUMMZYHULSUIZIMZTICQORLNTOVKVAMQTKHVRIFMNTSLYGHEHFAHWWATLYAPEXTHEPKJUGDVWUDDPRQLUZMSZOJPSIKAIHLTONYXAULECXXKWFQOIKELWOHRVRUCXIAASKHMWTMAJEWGEESLWRTQKVHRRCDYXNT 
LDSUPXMQTQDFAQAPYBGXPOLOCLFQNGNKPKOBHZWHRXAWAWJKMTJSLDLNHMUGVVOPSAMRUJEYUOBPFNEHPZZCLPNZKWMTCXERPZRFKSXVEZTYCXFRHRGEITWHRRYPWSVAYBUHCERJXDCYAVICPTNBGIODLYLMEYLISEYNXNMCDPJJRCTLYNFMJZQNCLAGHUDVLYIGASGXSZYPZKLAWQUDVNTWGFFY 
FFSMQWUNUPZRJMTHACFELGHDZEJWFDWVPYOZEVEJKQWHQAHOCIYWGVLPSHFESCGEUCJGYLGDWPIWIDWZZXRUFXERABQJOXZALQOCSAYBRHXQQGUDADYSORTYZQPWGMBLNAQOFODSNXSZFURUNPMZGHTAJUJROIGMRKIZHSFUSKIZJJTLGOEEPBMIXISDHOAIFNFEKKSLEXSJLSGLCYYFEQBKIZZTQQ 
XBQZAPXAAIFQEIXELQEZGFEPCKFPGXULLAHXTSRXDEMKFKABUTAABSLNQBNMXNEPODPGAORYJXCHCGKECLJVRBPRLHORREEIZOBSHDSCETTTNFTSMQPQIJBLKNZDMXOTRBNMTKHHCZQQMSLOAXJQKRHDGZVGITHYGVDXRTVBJEAHYBYRYKJAVXPOKHFFMEPHAGFOOPFNKQAUGYLVPWUJUPCUGGIXGR 
AMELUTEPYILBIUOCKKUUBJROQFTXMZRLXBAMHSDTEKRRIKZUFNLGTQAEUINMBPYTWXULQNIIRXHHGQDPENXAJNWXULFBNKBRINUMTRBFWBYVNKNKDFR 

Ich versuche, die kleinsten Teilzeichen ABCDA die Buchstaben enthalten, zu finden.

Ich versuchte eine Regex-Ansatz.

Dies funktioniert, aber es finden nur Strings wo ABCDA erscheinen (in dieser Reihenfolge). Bedeutung wird es nicht Teilzeichenfolge finden, wo die Buchstaben in einer Reihenfolge wie folgt angezeigt: BCDAA

Ich versuche, meine regex zu ändern, um dies zu berücksichtigen. Wie würde ich das tun, ohne | zu verwenden und all die verschiedenen Fälle einzugeben?

Answer 1

Sie können nicht.

Betrachten wir einen Sonderfall: Angenommen, die gesuchten Buchstaben sind A, A und B. Irgendwann in Ihrem Regexp wird es sicherlich eine B geben. Die Teile links und rechts von der B sind jedoch unabhängig voneinander, so dass Sie nicht von einer auf die andere verweisen können. Wie viele A s im subexpression rechts von den B ist abhängig von der Anzahl der A s Wesen bereits abgestimmt im linken Teil abgestimmt sind. Dies ist mit regulären Ausdrücken nicht möglich, also müssen Sie alle verschiedenen Befehle ausführen, die viele sein können!

Ein weiteres beliebtes Beispiel, das das Problem veranschaulicht ist mit Verschlussklammern öffnen Klammern zu entsprechen. Es ist nicht möglich, einen regulären Ausdruck zu schreiben, der angibt, dass in einer gegebenen Zeichenfolge auf eine Folge von öffnenden Klammern eine Folge von schließenden Klammern derselben Länge folgt. Der Grund dafür ist, dass die Klammern zählen Sie würden im Gegensatz zu einer endlichen Zustandsmaschine eine Stapelmaschine benötigen, aber reguläre Ausdrücke sind Muster beschränkt, die unter Verwendung von FSMs angepasst werden kann.

Answer 2

Vielleicht nicht ganz so klar regex wie die Verwendung könnte (für mich gut, regex sind nie wirklich klar: D) sein, das Sie Brute-Force (nicht so brachial)

Erstellen Sie einen Index von „gültig“ Punkte Ihrer verwenden string (diejenigen mit den gewünschten Buchstaben) und iterieren mit einer doppelten Schleife darüber, wobei Teilstrings mit mindestens 5 dieser Punkte erhalten werden, wobei geprüft wird, ob es sich um gültige Lösungen handelt. Vielleicht nicht der effizienteste Weg, aber einfach zu implementieren, zu verstehen und wahrscheinlich zu optimieren.

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

Dieser Algorithmus verwendet nicht einen regulären Ausdruck, fand aber auch beide Lösungen.

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