Randomized Algorithmus für die Zeichenfolge

Question

Frage passend:

ein Text t[1...n, 1...n] und p[1...m, 1...m] gegeben, n = 2m von Alphabet [0, Sigma-1], sagen wir p Streichhölzer t bei [i,j] wenn t[i+k-1, j+L-1] = p[k,L] für alle k,L. Entwerfen Sie einen randomisierten Algorithmus, um alle Treffer in O(n^2) Zeit mit hoher Wahrscheinlichkeit zu finden.

Image:

Kann jemand mir helfen, zu verstehen, was dieser Text bedeutet? Ich glaube, es sagt, dass 't' zwei Wörter enthält und das Muster auch zwei Wörter ist, aber die Länge beider Muster ist die Hälfte von 't'. Von hier verstehe ich jedoch nicht, wie die Reichweite von [i, j] ins Spiel kommt. Diese Aussage geht über meinen Kopf.

Dies könnte auch sagen, dass t und p 2D-Arrays sind und Sie versuchen, eine "Box" aus dem Muster in der t 2D-Array anzupassen.

Jede Hilfe wäre willkommen, danke!

Answer 1

Das Problem fordert Sie auf, eine 2D pattern zu finden, die durch das Array im t Array definiert ist, das ebenfalls 2D ist.

Die offensichtlichste zufällige Lösung für dieses Problem wäre, zwei zufällige Indizes i und j zu erzeugen und dann nach dem Muster von diesem (i, j) zu suchen.

Um redundante Suchen zu vermeiden, können Sie verfolgen, welche Paare von (i, j) Sie zuvor besucht haben. Dies kann mit einem einfachen 2D-Array erfolgen. Die Komplexität von oben wäre O(n^3) im schlimmsten Fall.

---

Sie können auch hashing verwenden, um die Saiten zum Vergleichen der Komplexität O(n^2) zu reduzieren.

Zuerst müssen Sie das Array t Zeile für Zeile hashen und den Wert in einem Array wie hastT speichern, dafür können Sie die verwenden.

Sie können das Array p dann mit dem Rolling-Hash-Algorithmus hashen und die Hashes Zeile für Zeile im Array hashP speichern.

Dann, wenn Sie das Zufallspaar zu generieren (i, j), können Sie die Hash-Wert des entsprechenden t Array erhalten können das Array hashT in linearer Zeit anstelle des Brute-Force-Vergleichs verwenden, die quadratische Zeit in Anspruch nimmt und vergleichen (Hinweis kann es Kollisionen in der seine Hash können Sie Brute Brute, wenn ein Hash übereinstimmt, um völlig sicher zu sein).

die entsprechende Hash finden die hashT verwenden wir folgende Möglichkeiten an, dass das aktuelle Paar (i, j)(3, 4) ist, und die Dimensionen des Arrays p2 x 3 sind.

Dann können wir hashT[3][7] - hash[3][3] == hashP[3] vergleichen, um das Ergebnis zu finden, die obige Logik kommt von der rolling hash algo.

Pseudocode für die Suche in linearer Zeit mit Hashing:

hashT[][], hashS[] 

i = rand(), j = rand(); 

for(int k = i;k < i + lengthOfColumn(p);i++){ 
    if((hashT[i][j + lengthOfRow(p)] - hashT[i][j-1]) != hashP[i]){ 
     //patter does not match. 
     return false; 
    } 
}