Número de substrings de una string

Encuentre el número total de substrings no vacías de una string con N caracteres. 

Entrada: str = “abc” 
Salida: 6 
Cada substring de la string dada: “a”, “b”, “c”, “ab”, “bc”, “abc”

Entrada: str = “abcd” 
Salida: 10 
Cada substring de la string dada: “a”, “b”, “c”, “d”, “ab”, “bc”, “cd”, “abc”, “ bcd” y “abcd”

El conteo de substrings no vacías es n*(n+1)/2
Si incluimos una string vacía también como substring, el conteo se convierte en n*(n+1)/2 + 1

¿Cómo funciona la fórmula anterior?  

1. El número de substrings de longitud uno es n (Podemos elegir cualquiera de los n caracteres)
2. El número de substrings de longitud dos es n-1 (Podemos elegir cualquiera de los n-1 pares formados por adyacentes)
3. El número de substrings de longitud tres es n-2 
   (Podemos elegir cualquiera de los n-2 tripletes formados por adyacentes)
4. En general, el número de substrings de longitud k es n-k+1 donde 1 <= k <= n

Número total de substrings de todas las longitudes de 1 a n = 
n + (n-1) + (n-2) + (n-3) + … 2 + 1 
= n * (n + 1)/2

C++

// CPP program to count number of substrings // of a string #include <bits/stdc++.h> using namespace std;    int countNonEmptySubstr(string str) {    int n = str.length();    return n*(n+1)/2; }    // driver code int main() {     string s = "abcde";     cout << countNonEmptySubstr(s);     return 0; }

Java

// Java program to count number of substrings // of a string import java.io.*;    public class GFG {            static int countNonEmptySubstr(String str)     {         int n = str.length();         return n * (n + 1) / 2;     }            // Driver code     public static void main(String args[])     {         String s = "abcde";         System.out.println(                   countNonEmptySubstr(s));     } }    // This code is contributed  // by Manish Shaw (manishshaw1)

Python3

# Python3 program to count number # of substrings of a string    def countNonEmptySubstr(str):     n = len(str);     return int(n * (n + 1) / 2);    # driver code s = "abcde"; print (countNonEmptySubstr(s));    # This code is contributed by # Manish Shaw (manishshaw1)

C#

// C# program to count number  // of substrings of a string using System; class GFG {            static int countNonEmptySubstr(string str)     {         int n = str.Length;         return n * (n + 1) / 2;     }            // Driver Code     public static void Main()     {         string s = "abcde";         Console.Write(countNonEmptySubstr(s));     } }    // This code is contributed  // by Manish Shaw (manishshaw1)

PHP

<?php // PHP program to count number // of substrings of a string    function countNonEmptySubstr($str) {     $n = strlen($str);     return $n * ($n + 1) / 2; }    // Driver Code $s = "abcde"; echo countNonEmptySubstr($s);        // This code is contributed by Anuj_67 ?>

JavaScript

<script>    // JavaScript program to count number of substrings // of a string function countNonEmptySubstr(str)     {         let n = str.length;         return n * (n + 1) / 2;     }            // Driver code         let s = "abcde";         document.write(countNonEmptySubstr(s));       // This code is contributed shivanisinghss2110    </script>

Producción: 

15

 

Complejidad Temporal: O(1).

Espacio Auxiliar: O(1).