Algorithmus zu finden, der am meisten common substrings in einem string

Dies ist als Aufgabe ähnlich der Nussinov-Algorithmus ist, und sogar noch einfacher, da wir nicht zulassen, dass irgendwelche Lücken, Einfügungen oder Unterschiede in der Ausrichtung.

Für die Schnur mit der Länge N, definieren Sie eine F[-1 .. N, -1 .. N] Tabelle und füllen Sie mit den folgenden Regeln:

  for i = 0 to N
    for j = 0 to N
      if i != j
        {
          if A[i] == A[j]
            F[i,j] = F [i-1,j-1] + 1;
          else
            F[i,j] = 0;
        }

Beispielsweise für B A O B A B:

Dieser läuft in O(n^2) Zeit. Die größten Werte in der Tabelle nun auf den end-Positionen der längste self-matching subquences (ich - das Ende einer Begebenheit, j - anderen). Am Anfang, das array wird angenommen, dass null initialisiert werden. Ich habe Hinzugefügt-Bedingung ausschließen, die Diagonale ist die längste, aber wohl nicht interessant-selbst-übereinstimmen.

Denken mehr, diese Tabelle ist symmetrisch über die Diagonale, so ist es genug, um zu berechnen, nur die Hälfte. Auch das array mit null initialisiert, so dass die Zuweisung von null ist redundant. Bleibt

  for i = 0 to N
    for j = i + 1 to N
      if A[i] == A[j]
         F[i,j] = F [i-1,j-1] + 1;

Kürzer, aber möglicherweise schwieriger zu verstehen. Die berechnete Tabelle enthält alle Spiele, kurze und lange. Sie können weitere Filterung, wie Sie benötigen.

Im nächsten Schritt müssen Sie sich zu erholen Zeichenfolgen, die aus dem nicht-null-Zellen, die nach oben und nach Links von der Diagonale. Während dieser Schritt ist auch trivial, um einige hashmap, um die Anzahl der selbst-ähnlichkeit entspricht, für die gleiche Zeichenfolge. Mit normalen string und normale minimale Länge nur kleine Anzahl von Zellen in einer Tabelle verarbeitet werden, wird durch diese Karte.

Ich denke, dass mit hashmap direkt tatsächlich erfordert O(n^3), wie die key-strings an das Ende des Zugangs verglichen werden müssen, irgendwie für Gleichstellung. Dieser Vergleich ist wahrscheinlich O(n).

nur pseudo-code, und das ist vielleicht nicht die schönste Lösung, aber würde ich lösen wie diese:

function separateWords(String incomingString) returns StringArray{
  //Code
}

function findMax(Map map) returns String{
  //Code
}

function mainAlgorithm(String incomingString) returns String{
    StringArray sArr = separateWords(incomingString);
    Map<String, Integer> map; //init with no content
    for(word: sArr){
        Integer count = map.get(word);
        if(count == null){
            map.put(word,1);
        } else {
            //remove if neccessary
            map.put(word,count++); 
        }
   }
   return findMax(map);
}

Wo die map enthalten kann ein Schlüssel-Wert-Paare, wie in der Java-HashMap.

Da für jeden substring einen String der Länge >= 2 der text enthält mindestens einen substring der Länge 2 mindestens so oft, brauchen wir nur zu untersuchen, Teilstrings der Länge 2.

val s = "hello world this is hello world. hello world repeats three times in this string!"

val li = s.sliding (2, 1).toList
//li: List[String] = List(he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " t", th, hi, is, "s ", " i", is, "s ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, d., ". ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " r", re, ep, pe, ea, at, ts, "s ", " t", th, hr, re, ee, "e ", " t", ti, im, me, es, "s ", " i", in, "n ", " t", th, hi, is, "s ", " s", st, tr, ri, in, ng, g!)

val uniques = li.toSet
uniques.toList.map (u => li.count (_ == u))
//res18: List[Int] = List(1, 2, 1, 1, 3, 1, 5, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 1, 3, 3, 2, 4, 1, 2, 2, 1)

uniques.toList(6)
res19: String = "s "