Print All Substring of the Given String

ā€œPrint all the substring of the Given Stringā€ is a popular technical interview problem asked in many interviews. Here, we are given a string of length ā€˜nā€™ and our task is to count and print all the substring of the given string. 

Example:

INPUT:
ABCD
OUTPUT:
No of substring: 10
Substrings: A, B, C, D, AB, BC, CD, ABC, BCD, ABCD

The steps required to count and print the substring of the string are as follows:

  1. Set count = 0.
  2. Three nested loops will be taken.
  3. The outer loop will be used to take the starting character of the substring.
  4. The middle loop will be used to take the last character of the substring.
  5. The inner loop will be used to print the substring from starting character (from outer loop) to ending character (from middle loop). Increment count by 1.

C++ Program to count and print all the substring of the string are as follows:

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    string str;  
    cout<<"Enter a string:\n";  
    cin>>str;  
    int count = 0;  
    cout<<"The substring are:\n";  
    int size = str.length();  
    /* Outer loop for starting character of substring */  
    for(int i = 0; i < size; i++)  
    {  
        /* Middle loop for ending character of substring */  
        for(int j = i; j < size; j++)  
        {  
            string substring = "";  
            /* Inner loop for creating substring */  
            for(int k = i; k <= j; k++)  
            {  
                substring = substring + str[k];  
            }  
            count++;  
            cout<<substring<<"\n";  
        }  
    }  
    cout<<"The number of substrings are "<<count;  
}  

OUTPUT:
Enter a string: ABCD
The substring are:
A
AB
ABC
ABCD
B
BC
BCD
C
CD
D
The number of substrings are 10
Time Complexity:
O(n^3), where n is the length of the string

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *