Für eine Zeichenfolge der Länge n lautet die Formel zur Berechnung aller Teilzeichenfolgen: n (n + 1) / 2 Kann mir jemand helfen, diese Formel intuitiv zu verstehen?
Wikipedia sagt: "Die Anzahl der Teilzeichenfolgen einer Zeichenfolge der Länge, in der Symbole nur einmal vorkommen, ist die Anzahl der Möglichkeiten, zwei verschiedene Stellen zwischen Symbolen zum Starten / Beenden der Teilzeichenfolge"
auszuwählenUm dies zu verstehen, beachten Sie, dass jeder Teilstring zwei Parameter benötigt: Startindex und Endindex.
Zum Beispiel: string str="Hallo Welt"; // Länge == 11
Beginnen wir damit, dass wir zur Zeit nur einen Teilzeichenkettenstring nehmen: H, e, l, l, o,, W, o, r, l, d. Dann mit 2 Zeichen zur Zeit: Er, el, ll, lo, o, W, Wo, oder, rl, ld. Dann nehmen Sie 3 Zeichen: Hel, etc ..
Also ist die Gesamtzahl der Teilstrings 11 + 10 + 9 + .. + 1 und im Allgemeinen for i from 1 to n , wir haben n - i + 1 Teilstrings. Durch die Zusammenfassung:
Sigma (n + 1 - i) von i = 1 bis n, ergibt n * (n + 1) - n * (n + 1) / 2 was n * (n + 1) / 2
Eine Teilzeichenkette wird durch die Position bestimmt, an der sie beginnt und an der sie in der ursprünglichen Zeichenkette endet. Für jede Teilkette haben wir diese zwei Endpunkte. Umgekehrt gibt es für zwei beliebige Zeichen in der Zeichenfolge genau eine Teilzeichenfolge, die an diesen Punkten beginnt und endet.
Somit ist die Anzahl aller Teilstrings die Anzahl aller Paare von (nicht notwendigen unterschiedlichen) Zeichen.
Es gibt n*(n-1)/2 Paare von unterschiedlichen Zeichen. Sie müssen auch die nicht eindeutigen Paare hinzufügen, die n sind.
Also ist die Gesamtanzahl n * (n-1) / 2 + n = n * (n+1) / 2 .
Ich bin nicht gut in Mathe, aber was sind substrings einer Zeichenkette und was sind die Möglichkeiten, substrings einer Zeichenkette zu bekommen, werde ich versuchen, Sie zu erklären.
lasst uns ein Beispiel nehmen: "MOBILE" Dies ist eine Zeichenkette aus 6 Zeichen, jetzt gemäß Ihrer Formel n (n + 1) / 2, was zu 6 (6 + 1) / 2 = 21
führtAlso ist die Teilzeichenfolge eine beliebige Zeichenfolge, die den Startindex und den Endindex zwischen der gesamten Zeichenfolge hat.
in der Zeichenfolge "MOBILE" folgt die Teilzeichenfolge, die wir haben können:
Schritt 1: "M" Startindex "M" und Endindex "M" dies ist eine Möglichkeit
Schritt 2: "MO" Startindex "M" und Endindex "O" dies ist zweite Möglichkeit
.
.
Schritt 5: "MOBIL" Startindex "M" und Endindex "L" ist die fünfte Möglichkeit
.
.
Schritt 8: "OB" Startindex "O" und Endindex "B" dies ist acht Möglichkeiten
.
.
Schritt 21: "MOBILE" Startindex "E" und Endindex "E" ist die einundzwanzigste Möglichkeit
Dies sind die Möglichkeiten, einen Teilstring innerhalb eines Strings zu haben und im Endindex des Teilstrings darf nicht kleiner als der Startindex sein.
Nun, es ist die Summe aller Teilstrings der Länge 1 (genau n), plus alle Teilstrings der Länge 2 (n-1), plus alle Teilstrings der Länge n (was eine richtige Zeichenkette ist). Dann haben Sie n + n-1 + n-2 ... + 1 = (n * (n + 1)) / 2
Die Summe kann mit natürlicher Induktion berechnet werden und es ist auch bekannt wegen Gauss, der diese Summe löste, als er in der Schule war.
Angenommen, Sie möchten die Teilzeichenfolge von "abc" herausfinden, das wäre {"a", "ab", "abc", "b", "bc", "c"} wir würden es mit dem folgenden Code berechnen
%Vor%Wenn Sie diesen Code betrachten, können Sie leicht erkennen, dass die Schleifen als
ausgeführt werden3 Mal im ersten Lauf, 2 Mal im zweiten Lauf, 1 Mal im dritten Lauf
Da jedes Mal ein Teilstring zurückgegeben wird, ist gleich der Summe von n das ist = n (n + 1) / 2
n * (n + 1) / 2 ist die Summe der Zahlen von 1 bis n.
Wenn n = 4, 4 * (4 + 1) / 2 = 10.
Hoffe, das hilft.
Tags und Links algorithm math combinations