Combien de sous-chaînes d'une chaîne de caractères

Combien de subtrings sont là dans une chaîne de caractères?

Why does string x [1:n] have O(n^2) subtrings in the lecture 21 Dynamic Programming III of        
6.006 from MIT? 
Why is not O(2^n)?

Voici un lien [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21.pdf]

Ce n'est pas vraiment approprié ici, pour plusieurs raisons. Pour l'un, si je suis en train de lire correctement, il fait référence à quelque chose à laquelle nous n'avons pas accès. Pour les deux, nous ne sommes pas des devoirs à faire des machines. Voir ici.
Une sous-chaîne est complètement définie par deux paramètres, tels que le début et la durée, dans l'intervalle [1:n], donc il n'y a pas plus de n^2 possibilités. Un général, non contigus, sous-ensemble a besoin de n vrai-faux décisions à le préciser, il y a donc 2^n possibilités.
Cette question semble être hors-sujet, car il est à propos de la combinatoire.
Ce n'est pas pour les devoirs. J'ai appris des matériaux par moi-même, mais je n'ai pas compris dans certains détails dans les notes de cours. Je donne le lien vers les notes de cours.
Cette question semble être hors-sujet, car il est à propos de la combinatoire

OriginalL'auteur zhushun0008 | 2014-07-23

  1. 16

    Simplement un sous-chaîne est définie par deux paramètres [i,j] qui sont les index de début et de fin de l'index pour sous-chaîne dans la chaîne d'origine . Maintenant 0<=i,j<=n que les indices devraient être au sein de la chaîne, le Total des valeurs i&j chacun peut avoir sont n donc toutes les combinaisons de [i,j] serait n*n qui est O(n^2)

    Aussi, je < j donc ce n'est pas exact. Et 0,0 le cas trivial ne compte pas.
    Gi0rgi0s je sais , c'était juste un ordre d'analyse donc pas besoin d'aller dans les détails

    OriginalL'auteur Vikram Bhat

  2. 30

    Prendre une chaîne de longueur n=4, dire: "ABCD"

    Les sous-chaînes de la ci-dessus sont (en longueur):

    • 1 caractères: A,B,C,D (4 sous-chaînes)
    • 2 caractère: AB,BC,CD, (3 sous-chaînes)
    • 3 caractère: ABC,BCD (2 sous-chaînes)
    • 4 caractères: ABCD (1 sous-chaîne)

    Totalisant le nombre des rendements: 1+2+3+4 = 10.

    Donc, pour généraliser, le nombre de sous-chaînes est la somme de tous les nombres entiers de 1 à n.

    Cette somme est calculée selon la formule (n^2 + n) /2 (voir ici: Somme de deux Nombres Consécutifs)

    De sorte que le rendement est de l' n^2 ordre de grandeur.

    C'est de loin supérieur à la réponse que l'on a accepté la réponse. C'est le seul qui doit avoir été accepté!
    En regardant ça, je me demande...est la chaîne complète d'une sous-chaîne? si non, puis de soustraire un de la réponse.
    Ou ajouter 1 pour la chaîne vide ""

    OriginalL'auteur Gi0rgi0s

  3. 5

    Donné une chaîne de n éléments,

    Si vous commencez avec le 1er élément, vous pouvez le formulaire n chaînes

    Si vous commencez avec un 2ème élément, vous pouvez le formulaire n-1 chaînes de caractères
    .... ainsi de suite...

    Prenez, par exemple, 1234

    1,12,123,1234

    2,23,234

    3,34

    4

    Comme vous pouvez le voir, le total est n + (n-1) + (n-2) ...1 c'est à dire somme de n éléments qui est n(n+1)/2

    OriginalL'auteur blueskin

  4. 1

    vous pourriez avoir été confondu avec le nombre de sous-ensembles d'un ensemble, mais il est apparemment importante ici que ce sont les sous-chaînes qui ont fixé le modèle et la valeur que vous pensez que 2^n, qui sera le nombre de sous-séquences de la chaîne.

    OriginalL'auteur saurabh kumar

  5. -3

    Il y a autant de chaînes que vous voulez obtenir. Commençant et se terminant à un index.

    string.Substring(0, 10); //untill 10th character, and so on

    http://msdn.microsoft.com/en-us/library/aka44szs(v=vs. 110).aspx

    Si vous essayez d'obtenir l'aide de la chaîne foreach vous obtiendrez chaque chaîne coupée en deux à l'espace. Ainsi, l'espace de caractères spécifier le nombre de chaînes de caractères dans une chaîne. 

    string strngs = "Love for all, Hatred for none!";

foreach (string strng in strngs) {
   Console.WriteLine(strng);
}

//(Expected) Output
//Love
//for
//all,
//Hatred
//for
//none!
    Toute fonction python disponible?

    OriginalL'auteur Afzaal Ahmad Zeeshan