Suche nach Teilstrings eines string

Für einen string der Länge n, die Formel, um zu berechnen, werden alle Teilzeichenfolgen sind: n(n+1)/2
Kann mir jemand helfen in der intuitiv verstehen diese Formel?

Wikipedia sagt:
"Die Anzahl der Teilstrings einer Zeichenkette der Länge, wo die Symbole nur einmal vorkommen, ist die Anzahl der Möglichkeiten zu wählen Sie zwei unterschiedliche stellen zwischen den Symbolen für start/Ende der substring"

InformationsquelleAutor Chander Shivdasani | 2012-09-14
  1. 35

    Um dies zu verstehen, beachten Sie, dass jede Teilfolge benötigt zwei Parameter: start-index und end-index.

    Beispiel: string str = "Hallo Welt"; //length == 11

    Können beginnen, indem Sie nur eine Zeichen Teilzeichenfolge in der Zeit: H, e, l, l, o , W, o, r, l, d.... Dann durch die Einnahme von 2 Zeichen zur Zeit: Er, el, ll, lo, o , W, Wo, oder, rl, ld. Dann durch die Einnahme von 3 chars: Hel, .. etc.

    Damit die gesamte substring count ist 11 + 10 + 9 + .. + 1 und, im Allgemeinen, for i from 1 to n haben wir n - i + 1 Teilstrings. Durch summition:

    Sigma (n + 1 - i) von i = 1 bis n ergibt n * (n + 1) - n * (n + 1) /2 die n * (n + 1) /2

    InformationsquelleAutor
  2. 4

    Eines Teilstrings ermittelt wird, wo es beginnt und wo es endet in der original-string.
    Für jeden Teilstring, haben wir diese beiden Endpunkte. Umgekehrt, wenn zwei Zeichen in der Zeichenfolge, es gibt genau einen substring, der beginnt und endet an den Punkten.

    Also die Anzahl aller Zeichenketten ist die Anzahl aller Paare von (nicht notwendig verschiedenen) Zeichen.

    Gibt es n*(n-1)/2 paar deutliche Zeichen. Sie müssen auch hinzufügen, die nicht unterschiedliche Paare, die n.

    So dass die Gesamtzahl ist n * (n-1) /2 + n = n * (n+1) /2.

    InformationsquelleAutor Petar Ivanov
  3. 1

    Ich bin nicht gut in Mathe, aber was sind substrings ein string und was sind die Möglichkeiten, sich substrings einer Schnur ich werde versuchen zu erklären, Sie.

    nehmen wir ein Beispiel: "MOBILE" dies ist ein string mit 6 Zeichen, jetzt nach der Formel
    n(n+1)/2, die Ergebnisse 6(6+1)/2=21

    Also die Teilfolge ist eine beliebige Zeichenfolge, die start-index und end-index zwischen den ganzen string.

    string "MOBILE" folgenden sind die Teilfolge, die wir haben können :

    Schritt 1: "M" start-index "M" - und Ende-index "M" dies ist eine Möglichkeit

    Schritt 2: "MO" start-index "M" - und Ende-index "O" das ist die zweite Möglichkeit

    .

    .

    Schritt 5: "MOBIL" start-index "M" - und Ende-index "L" dies ist der fünfte Möglichkeit

    .

    .

    Schritt 8: "OB" start-index "O" - und Ende-index "B" dies ist acht Möglichkeit

    .

    .

    Schritt 21:"MOBILE" start-index "E" - und Ende-index "E" das ist zwanzig erste Möglichkeit

    Dies sind die Möglichkeiten, um einen substring in einem string und substring-end-index darf nicht kleiner als Beginn-index.

    InformationsquelleAutor FosterZ
  4. 1

    Gut, Es ist die Summe aller Zeichenketten der Länge 1 (genau n),
    plus alle Teilstrings der Länge 2 (n-1),
    plus alle substrings der Länge n (das ist eine richtige string). Dann haben Sie n + n-1 + n-2 ... + 1 = (n * (n+1)) /2

    Kann die Summe berechnet werden, die mittels natürlicher Induktion und es ist auch bekannt durch Gauss, der gelöst wird diese Summe, wenn er in der Schule war.

    • hast du meinen n*(n+1)/2?
    • Recht. 🙂 n * (n+1) / 2
    InformationsquelleAutor Luixv
  5. 0

    Angenommen, Sie möchten, um herauszufinden, den Teilstring "abc",
    das wäre
    {"a","ab","abc","b","bc","c"}
    wir würden uns berechnen, indem Sie den folgenden code

    for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){

        }
    }

    Suchen auf diesem code, es ist einfach zu sagen, dass die loops laufen als

    3 mal in der ersten Ausführung,
    2-mal in der Sekunde laufen,1 mal im Dritten laufen

    Als es gibt einen Teilstring immer,daher es ist gleich der Summe der n
    das ist = n(n + 1) /2

    InformationsquelleAutor Aditya
  6. -3

    n*(n+1)/2 ist die Summe der zahlen von 1 bis n.

    Wenn n = 4, 4 * (4 + 1) /2 = 10.

    Hoffe, das hilft.

    InformationsquelleAutor Arun B Chandrasekaran
Schreibe einen Kommentar