Data Structures and Algorithms (Some Questions for You - Answer to Question 1) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Write an algorithm to find a substring in a given string.

Given a string as an input. We need to write a program that will print all non-empty substrings of that given string.

Examples : 

Input :  abcd
Output :  a 
          b
          c
          d
          ab
          bc
          cd
          abc
          bcd
          abcd

We can run three nested loops, the outermost loop picks a starting character, mid-loop considers all characters on the right of the picked character as the ending character of the substring. The innermost loop prints characters from the currently picked starting point to the picked ending point. 

Implementation:

// C++ program to print all possible

// substrings of a given string

 

#include<bits/stdc++.h>

using namespace std;

 

// Function to print all sub strings

void subString(char str[], int n)

{

    // Pick starting point

    for (int len = 1; len <= n; len++)

    {   

        // Pick ending point

        for (int i = 0; i <= n - len; i++)

        {

            //  Print characters from current

            // starting point to current ending

            // point. 

            int j = i + len - 1;           

            for (int k = i; k <= j; k++)

                cout << str[k];

             

            cout << endl;

        }

    }

}

 

// Driver program to test above function

int main()

{

    char str[] = "abc";

    subString(str, strlen(str));

    return 0;

}




Output

a
b
c
ab
bc
abc

Time complexity: O( n3 )
Auxiliary Space: O(1)

Method 2 (Using substr() function): s.substr(i, len) prints substring of length ‘len’ starting from index i in string s.

Implementation:

• C++
• Java
• Python3
• C#
• Javascript

// C++ program to print all possible // substrings of a given string #include<bits/stdc++.h> using namespace std;   // Function to print all sub strings void subString(string s, int n) {     // Pick starting point in outer loop     // and lengths of different strings for     // a given starting point     for (int i = 0; i < n; i++)         for (int len = 1; len <= n - i; len++)             cout << s.substr(i, len) << endl; }   // Driver program to test above function int main() {     string s = "abcd";     subString(s,s.length());     return 0; }

Output

a
ab
abc
abcd
b
bc
bcd
c
cd
d

Time complexity: O( n3 )
Auxiliary Space: O(1)

Method 3 (Generate a substring using the previous substring):

Implementation:

• C++
• Java
• Python3
• C#
• Javascript

/*  * C++ program to print all possible  * substrings of a given string  * without checking for duplication.  */   #include<bits/stdc++.h> using namespace std;   /*  * Function to print all (n * (n + 1)) / 2  * substrings of a given string s of length n.  */ void printAllSubstrings(string s, int n) {     /*      * Fix start index in outer loop.      * Reveal new character in inner loop till end of string.      * Print till-now-formed string.      */     for (int i = 0; i < n; i++)     {         char temp[n - i + 1];         int tempindex = 0;         for (int j = i; j < n; j++)         {             temp[tempindex++] = s[j];             temp[tempindex] = '\0';             printf("%s\n", temp);         }     } }   // Driver program to test above function int main() {     string s = "Geeky";     printAllSubstrings(s, s.length());     return 0; }

Output

G
Ge
Gee
Geek
Geeky
e
ee
eek
eeky
e
ek
eky
k
ky
y

Time complexity: O( n2 )

Auxiliary Space: O(n)

Method 4 (using three nested loops):

Implementation:

• C++
• C
• Java
• Python3
• C#
• Javascript

// C program for the above approach #include <stdio.h> void printSubstrings(char str[]) {           // outermost for loop     // this is for the selection     // of starting point     for (int start = 0; str[start] != '\0'; start++) {                   // 2nd for loop is for selection         // of ending point         for (int end = start; str[end] != '\0'; end++) {                           // 3rd loop is for printing from             // starting point to ending point             for (int i = start; i <= end; i++) {                 printf("%c", str[i]);             }                         // changing the line after printing             // from starting point to ending point             printf("\n");         }     } }   // Driver Code int main() {       // code     char str[] = { 'a', 'b', 'c', 'd', '\0' };     // calling the method to print the substring     printSubstrings(str);     return 0; }

Output

a
ab
abc
abcd
b
bc
bcd
c
cd
d

Time complexity: O(N3), where N is the length of the input string
Auxiliary Space: O(1)

Method 5 (Using two nested loops):

Implementation:

• C++
• Java
• Python3
• C#
• Javascript

// CPP program for the above approach   #include <iostream>   using namespace std;   void printSubstrings(string str) {       // First loop for starting index     for (int i = 0; i < str.length(); i++) {         string subStr;         // Second loop is generating sub-string         for (int j = i; j < str.length(); j++) {             subStr += str[j];             cout << subStr << endl;         }     } }   // Driver Code   int main() {     string str = "abcd";     printSubstrings(str);     return 0;     //    this code is contributed by defcdr }

Output

a
ab
abc
abcd
b
bc
bcd
c
cd
d

Time complexity: O(N2), where N is the length of the input string.
Auxiliary Space: O(N), where N is the length of the input string.

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds