Algorithmus zum Auffinden des kleinsten Snippets beim Durchsuchen eines Dokuments?

Question

Ich habe Skienas ausgezeichnetes "The Algorithm Design Manual" durchgelesen und bin bei einer der Übungen hängen geblieben.

Die Frage ist: "Finden Sie bei einem Suchbegriff aus drei Wörtern den kleinsten Ausschnitt des Dokuments, der alle drei Suchbegriffe enthält, d. h. den Ausschnitt mit der geringsten Anzahl von Wörtern. Sie erhalten die Indexpositionen, an denen diese Wörter in den Suchstrings vorkommen, z. B. Wort1: (1, 4, 5), Wort2: (4, 9, 10) und Wort3: (5, 6, 15). Jede der Listen ist in der oben genannten Reihenfolge sortiert."

Alles, was mir einfällt, ist O(n^2)... Diese Frage steht im Kapitel "Sortieren und Suchen", also nehme ich an, dass es einen einfachen und cleveren Weg gibt, dies zu tun. Ich versuche gerade etwas mit Graphen, aber das scheint zu viel zu sein.

Ideen? Danke

Answer 1

Die anderen Antworten sind in Ordnung, aber wenn man wie ich Probleme hat, die Frage überhaupt zu verstehen, sind sie nicht wirklich hilfreich. Lassen Sie uns die Frage neu formulieren:

Geben Sie drei Mengen von ganzen Zahlen an (nennen Sie sie A, B und C) und finden Sie den kleinsten zusammenhängenden Bereich, der ein Element aus jeder Menge enthält.

Es herrscht einige Verwirrung darüber, was die drei Sätze sind. In der 2. Auflage des Buches werden sie als {1, 4, 5} , {4, 9, 10} und {5, 6, 15} . Eine andere Version, die in einem Kommentar oben genannt wurde, lautet jedoch {1, 4, 5} , {3, 9, 10} und {2, 6, 15} . Wenn ein Wort kein Suffix/Präfix eines anderen Wortes ist, ist Variante 1 nicht möglich, also nehmen wir die zweite Variante.

Da ein Bild mehr sagt als tausend Worte, stellen wir die Punkte dar:

Wenn wir die obigen Ausführungen visuell betrachten, können wir feststellen, dass es zwei Antworten auf diese Frage gibt: [1,3] et [2,4] , beide der Größe 3 (drei Punkte in jedem Bereich).

Und nun der Algorithmus. Die Idee ist, mit dem kleinsten gültigen Bereich zu beginnen und ihn schrittweise zu verkleinern, indem die linke Grenze nach innen verschoben wird. Wir verwenden eine nullbasierte Indizierung.

MIN-RANGE(A, B, C)
  i = j = k = 0
  minSize = +

  while i, j, k is a valid index of the respective arrays, do
    ans = (A[i], B[j], C[k])
    size = max(ans) - min(ans) + 1
    minSize = min(size, minSize)
    x = argmin(ans)
    increment x by 1
  done

  return minSize

donde argmin ist der Index des kleinsten Elements in ans .

+---+---+---+---+--------------------+---------+
| n | i | j | k | (A[i], B[j], C[k]) | minSize |
+---+---+---+---+--------------------+---------+
| 1 | 0 | 0 | 0 | (1, 3, 2)          | 3       |
+---+---+---+---+--------------------+---------+
| 2 | 1 | 0 | 0 | (4, 3, 2)          | 3       |
+---+---+---+---+--------------------+---------+
| 3 | 1 | 0 | 1 | (4, 3, 6)          | 4       |
+---+---+---+---+--------------------+---------+
| 4 | 1 | 1 | 1 | (4, 9, 6)          | 6       |
+---+---+---+---+--------------------+---------+
| 5 | 2 | 1 | 1 | (5, 9, 6)          | 5       |
+---+---+---+---+--------------------+---------+
| 6 | 3 | 1 | 1 |                    |         |
+---+---+---+---+--------------------+---------+

n = Iteration

Bei jedem Schritt wird einer der drei Indizes inkrementiert, so dass der Algorithmus garantiert zu einem Ende kommt. Im schlimmsten Fall, i , j und k werden in dieser Reihenfolge inkrementiert, und der Algorithmus läuft in O(n^2) (in diesem Fall 9) Zeit. Für das gegebene Beispiel endet es nach 5 Iterationen.

Answer 2

O(n)

Pair find(int[][] indices) {
pair.lBound = max int;
pair.rBound = 0;
index = 0;

for i from 0 to indices.lenght{
    if(pair.lBound > indices[i][0]){
        pair.lBound = indices[i][0]
        index = i;
    }
    if(indices[index].lenght > 0)
        pair.rBound = max(pair.rBound, indices[i][0])
}
remove indices[index][0]

return min(pair, find(indices)}