recherche de sous-chaînes d'une chaîne
Pour une chaîne de longueur n, la formule pour calculer toutes les sous-chaînes sont: n(n+1)/2
Quelqu'un peut-il m'aider à comprendre intuitivement cette formule?
Dit Wikipedia:
"Le nombre de sous-chaînes d'une chaîne de caractères de longueur où les symboles ne se produisent une fois, est le nombre de façons de choisir deux endroits distincts entre les symboles de début/la fin de la sous-chaîne"
Consultez ce lien, où ils parlent de la formule n(n+1)/2, pour un autre morceau de l'information: maths.surrey.ac.uk/hosted-sites/R.Knott/runsums/triNbProof.html
OriginalL'auteur Chander Shivdasani | 2012-09-14
Vous devez vous connecter pour publier un commentaire.
À comprendre, notons que tout sous-chaîne a besoin de deux paramètres: index de début et de fin de l'index.
Par exemple: string str = "Hello World"; //longueur == 11
Permet de commencer par prendre un seul-sous-chaîne de caractères à l'instant: H, e, l, l, o , W, o, r, l, d. Puis par la prise de 2 caractères au temps: Il a, el, ll, lo, o , o, W, Wo, ou, rl, ld. Alors en prenant les 3 caractères: Hel, etc ..
De sorte que le total de la sous-chaîne de comptage est 11 + 10 + 9 + .. + 1 et, en général,
for i from 1 to n
, nous avonsn - i + 1
sous-chaînes. Par summition:Sigma (n + 1 - i) de i = 1 à n, les rendements
n * (n + 1) - n * (n + 1) /2
qui estn * (n + 1) /2
OriginalL'auteur
Une sous-chaîne est déterminée par l'endroit où il commence et où il se termine dans la chaîne d'origine.
Pour tout sous-chaîne que nous avons ces deux points d'extrémité. À l'inverse, pour les deux caractères dans la chaîne il y a exactement un sous-chaîne qui commence et se termine à ces points.
Ainsi que le nombre de sous-chaînes est le nombre de toutes les paires d' (pas nécessairement distincts) caractères.
Il y a
n*(n-1)/2
paires de caractères distincts. Vous devez également ajouter la non-paires, qui sont n.De sorte que le nombre total est de
n * (n-1) /2 + n = n * (n+1) /2
.OriginalL'auteur Petar Ivanov
Je ne suis pas bon en maths, mais ce sont
substrings
d'une chaîne et quelles sont les possibilités pour obtenirsubstrings
d'une chaîne, je vais essayer de vous expliquer.prenons un exemple: le "MOBILE" ceci est une chaîne de 6 caractères, maintenant en fonction de votre formule
n(n+1)/2 résultats 6(6+1)/2=21
Si la sous-chaîne est une chaîne de caractères qui a index de début et de fin d'indice entre l'ensemble de la chaîne.
en chaîne "MOBILE" sont les suivantes substring nous pouvons avoir :
étape 1: "M" de début de l'indice "M" et à la fin de l'indice "M" c'est une possibilité
étape 2: le "MO" de début de l'indice "M" et à la fin de l'indice "O" ceci est la deuxième possibilité
.
.
l'étape 5: "MOBIL" début de l'indice "M" et à la fin de l'indice "L" c'est la cinquième possibilité
.
.
étape 8: "OB" index de début "O" et à la fin de l'indice "B" c'est huit possibilité
.
.
étape 21:"MOBILE" de début de l'indice "E" et à la fin de l'index "E" c'est la vingt-et-unième possibilité
Ce sont les possibilités d'avoir une sous-chaîne dans une chaîne et dans la sous-chaîne de la fin de l'index ne peut pas être inférieure index de début.
OriginalL'auteur FosterZ
Bien, C'est la somme de toutes les sous-chaînes de longueur 1 (n),
en plus de toutes les sous-chaînes de longueur 2 (n-1),
en plus de toutes les sous-chaînes de longueur n (qui est une chaîne correcte). Ensuite, vous avez n + n-1 + n-2 ... + 1 = (n * (n+1)) /2
La somme peut être calculée à l'aide de naturel induction et il est également connu en raison de Gauss qui a résolu cette somme, quand il était à l'école.
la droite. 🙂 n * (n+1) / 2
OriginalL'auteur Luixv
Supposons que vous voulez savoir sous-chaîne "abc",
que serait
{"a","ab","abc","b","bc","c"}
on calcule par le code suivant
En regardant ce code, il est facile de dire que les boucles exécuter en tant qu'
Car il renvoie une sous-chaîne à chaque fois,donc il est égal à la somme des n
qui est = n(n + 1) /2
OriginalL'auteur Aditya
n*(n+1)/2 est la somme des nombres de 1 à n.
Si n = 4, 4 * (4 + 1) /2 = 10.
Espère que cette aide.
OriginalL'auteur Arun B Chandrasekaran