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 : abcdOutput : a b c d ab bc cd abc bcd abcd
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
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++
// 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;
}
Java
//Java program to print all possible
// substrings of a given string
class GFG {
// Function to print all sub strings
static 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++) {
System.out.print(str[k]);
}
System.out.println();
}
}
}
// Driver program to test above function
public static void main(String[] args) {
char str[] = {'a', 'b', 'c'};
subString(str, str.length);
}
}
// This code is contributed by PrinciRaj1992
Python
# Python3 program to print all possible
# substrings of a given string
# Function to print all sub strings
def subString(Str,n):
# Pick starting point
for Len in range(1,n + 1):
# Pick ending point
for i in range(n - Len + 1):
# Print characters from current
# starting point to current ending
# point.
j = i + Len - 1
for k in range(i,j + 1):
print(Str[k],end="")
print()
# Driver program to test above function
Str = "abc"
subString(Str,len(Str))
# This code is contributed by mohit kumar
C#
// C# program to print all possible
// substrings of a given string
using System;
public class GFG {
// Function to print all sub
// strings
static void subString(string 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++)
Console.Write(str[k]);
Console.WriteLine();
}
}
}
// Driver program to test
// above function
static public void Main ()
{
string str = "abc";
subString(str, str.Length);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to print all possible
// substrings of a given string
// Function to print all sub strings
function subString($str, $n)
{
// Pick starting point
for ($len = 1; $len <= $n; $len++)
{
// Pick ending point
for ($i = 0; $i <= $n - $len; $i++)
{
// Print characters from current
// starting point to current ending
// point.
$j = $i + $len - 1;
for ($k = $i; $k <= $j; $k++)
echo $str[$k];
echo "\n";
}
}
}
// Driver Code
$str = "abc";
subString($str, strlen($str));
// This code is contributed by nitin mittal.
?>
Javascript
<script>
//Javascript program to print all possible
// substrings of a given string
// Function to print all sub strings
function subString(str,n)
{
// Pick starting point
for (let len = 1; len <= n; len++) {
// Pick ending point
for (let i = 0; i <= n - len; i++) {
// Print characters from current
// starting point to current ending
// point.
let j = i + len - 1;
for (let k = i; k <= j; k++) {
document.write(str[k]);
}
document.write("<br>");
}
}
}
// Driver program to test above function
let str=['a', 'b', 'c'];
subString(str, str.length);
// This code is contributed by patel2127
</script>
Output
abcabbcabc
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++
// 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;
}
Java
// Java program to print all substrings of a string
public class GFG {
// Function to print all substring
public static void SubString(String str, int n)
{
for (int i = 0; i < n; i++)
for (int j = i+1; j <= n; j++)
// Please refer below article for details
// of substr in Java
// https://www.geeksforgeeks.org/java-lang-string-substring-java/
System.out.println(str.substring(i, j));
}
public static void main(String[] args)
{
String str = "abcd";
SubString(str, str.length());
}
}
// This code is contributed by ASHISH KUMAR PATEL
Python3
# Python program to print all possible
# substrings of a given string
# Function to print all sub strings
def subString(s, n):
# Pick starting point in outer loop
# and lengths of different strings for
# a given starting point
for i in range(n):
for len in range(i+1,n+1):
print(s[i: len]);
# Driver program to test above function
s = "abcd";
subString(s,len(s));
# This code is contributed by princiraj1992
C#
// C# program to print all substrings of a string
using System;
public class GFG {
// Function to print all substring
public static void SubString(String str, int n)
{
for (int i = 0; i < n; i++)
for (int j = 1; j <= n - i; j++)
// Please refer below article for details
// of substr in Java
// https://www.geeksforgeeks.org/java-lang-string-substring-java/
Console.WriteLine(str.Substring(i, j));
}
public static void Main()
{
String str = "abcd";
SubString(str, str.Length);
}
}
/*This code is contributed by PrinciRaj1992*/
Javascript
<script>
// javascript program to print all substrings of a string
// Function to print all substring
function SubString( str , n)
{
for (var i = 0; i < n; i++)
for (var j = i+1; j <= n; j++)
// Please refer below article for details
// of substr in Java
// https://www.geeksforgeeks.org/java-lang-string-substring-java/
document.write(str.substring(i, j)+"<br/>");
}
var str = "abcd";
SubString(str, str.length);
// This code is contributed by gauravrajput1
</script>
Output
aababcabcdbbcbcdccdd
Time complexity: O( n3 )
Auxiliary Space: O(1)
This method is contributed by Ravi Shankar Rai
Method 3 (Generate a substring using the previous substring):
Implementation:
C++
/*
* 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;
}
Java
// Java program to print all possible
// subStrings of a given String
// without checking for duplication.
import java.io.*;
class GFG{
// Function to print all (n * (n + 1)) / 2
// subStrings of a given String s of length n.
public static 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 = new char[n - i + 1];
int tempindex = 0;
for(int j = i; j < n; j++)
{
temp[tempindex++] = s.charAt(j);
temp[tempindex] = '\0';
System.out.println(temp);
}
}
}
// Driver code
public static void main(String[] args)
{
String s = "Geeky";
printAllSubStrings(s, s.length());
}
}
// This code is contributed by avanitrachhadiya2155
Python3
'''
* Python3 program to print all possible
* substrings of a given string
* without checking for duplication.
'''
'''
* Function to print all (n * (n + 1)) / 2
* substrings of a given string s of length n.
'''
def printAllSubstrings(s, n):
# Fix start index in outer loop.
# Reveal new character in inner loop till end of string.
# Print till-now-formed string.
for i in range(n):
temp=""
for j in range(i,n):
temp+=s[j]
print(temp)
# Driver program to test above function
s = "Geeky"
printAllSubstrings(s, len(s))
# This code is contributed by shubhamsingh10
C#
// C# program to print all possible
// subStrings of a given String
// without checking for duplication.
using System;
class GFG{
// Function to print all (n * (n + 1)) / 2
// subStrings of a given String s of length n.
public static 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 = new char[n - i + 1];
int tempindex = 0;
for(int j = i; j < n; j++)
{
temp[tempindex++] = s[j];
temp[tempindex] = '\0';
Console.WriteLine(temp);
}
}
}
// Driver code
public static void Main()
{
String s = "Geeky";
printAllSubStrings(s, s.Length);
}
}
// This code is contributed by Shubhamsingh10
Javascript
<script>
// Javascript program to print all possible
// subStrings of a given String
// without checking for duplication.
// Function to print all (n * (n + 1)) / 2
// subStrings of a given String s of length n.
function printAllSubStrings(s, n)
{
// Fix start index in outer loop.
// Reveal new character in inner
// loop till end of String.
// Print till-now-formed String.
for(let i = 0; i < n; i++)
{
let temp = new Array(n - i + 1);
let tempindex = 0;
for(let j = i; j < n; j++)
{
temp[tempindex++] = s[j];
temp[tempindex] = '\0';
document.write(temp.join("") + "</br>");
}
}
}
let s = "Geeky";
printAllSubStrings(s, s.length);
</script>
Output
GGeGeeGeekGeekyeeeeekeekyeekekykkyy
Time complexity: O( n2 )
Auxiliary Space: O(n)
Method 4 (using three nested loops):
Implementation:
C++
// CPP program for the above approach
#include <iostream>
using namespace std;
void printSubstrings(string str)
{
// finding the length of the string
int n = str.length();
// outermost for loop
// this is for the selection
// of starting point
for (int i = 0; i < n; i++) {
// 2nd for loop is for selection
// of ending point
for (int j = i; j < n; j++) {
// 3rd loop is for printing from
// starting point to ending point
for (int k = i; k <= j; k++) {
cout << str[k];
}
// changing the line after printing
// from starting point to ending point
cout << endl;
}
}
}
// Driver Code
int main()
{
string str = "abcd";
printSubstrings(str);
return 0;
}
C
// 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;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
public static void printSubstrings(String str)
{
// finding the length of the string
int n = str.length();
// outermost for loop
// this is for the selection
// of starting point
for (int i = 0; i < n; i++) {
// 2nd for loop is for selection
// of ending point
for (int j = i; j < n; j++) {
// 3rd loop is for printing from
// starting point to ending point
for (int k = i; k <= j; k++) {
System.out.print(str.charAt(k));
}
// changing the line after printing
// from starting point to ending point
System.out.println();
}
}
}
// Driver Code
public static void main(String[] args)
{
String str = "abcd";
// calling method for printing substring
printSubstrings(str);
}
}
Python3
# Python program for the above approach
def printSubstrings(string, n):
# this is for the selection
# of starting point
for i in range(n):
# 2nd for loop is for selection
# of ending point
for j in range(i, n):
# 3rd loop is for printing from
# starting point to ending point
for k in range(i, (j + 1)):
print(string[k], end="")
# changing the line after printing
# from starting point to ending point
print()
# Driver Code
string = "abcd"
# calling the method to print the substring
printSubstrings(string, len(string))
C#
// C# program for the above approach
using System;
public class GFG {
public static void printSubstrings(String str)
{
// finding the length of the string
int n = str.Length;
// outermost for loop
// this is for the selection
// of starting point
for (int i = 0; i < n; i++) {
// 2nd for loop is for selection
// of ending point
for (int j = i; j < n; j++) {
// 3rd loop is for printing from
// starting point to ending point
for (int k = i; k <= j; k++) {
Console.Write(str[k]);
}
// changing the line after printing
// from starting point to ending point
Console.WriteLine();
}
}
}
// Driver Code
public static void Main(String[] args)
{
String str = "abcd";
// calling method for printing substring
printSubstrings(str);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
function printSubstrings(str)
{
// finding the length of the string
var n = str.length;
// outermost for loop
// this is for the selection
// of starting point
for (var i = 0; i < n; i++) {
// 2nd for loop is for selection
// of ending point
for (var j = i; j < n; j++) {
// 3rd loop is for printing from
// starting point to ending point
for (var k = i; k <= j; k++) {
document.write(str.charAt(k));
}
// changing the line after printing
// from starting point to ending point
document.write("<br>");
}
}
}
// Driver Code
var str = "abcd";
// calling method for printing substring
printSubstrings(str);
// This code is contributed by shivanisinghss2110
</script>
Output
aababcabcdbbcbcdccdd
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++
// 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
}
Java
// JAVA program for the above approach
import java.util.*;
class GFG{
static 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.charAt(j);
System.out.print(subStr +"\n");
}
}
}
// Driver Code
public static void main(String[] args)
{
String str = "abcd";
printSubStrings(str);
}
}
// This code is contributed by gauravrajput1
Python3
# Python program for the above approach
def printSubStrings(str):
# First loop for starting index
for i in range(len(str)):
subStr = "";
# Second loop is generating sub-String
for j in range(i,len(str)):
subStr += str[j];
print(subStr + "");
# Driver Code
if __name__ == '__main__':
str = "abcd";
printSubStrings(str);
# This code is contributed by umadevi9616
C#
// C# program for the above approach
using System;
public class GFG{
static 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];
Console.Write(subStr +"\n");
}
}
}
// Driver Code
public static void Main(String[] args)
{
String str = "abcd";
printSubStrings(str);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program for the above approach
function printSubStrings( str) {
// First loop for starting index
for (i = 0; i < str.length; i++) {
var subStr = "";
// Second loop is generating sub-String
for (var j = i; j < str.length; j++) {
subStr += str.charAt(j);
document.write(subStr + "<br/>");
}
}
}
// Driver Code
var str = "abcd";
printSubStrings(str);
// This code is contributed by gauravrajput1
</script>
Output
aababcabcdbbcbcdccdd
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.
My Personal Notesarrow_drop_up
FAQs
How to print all substrings of a string in C? ›
- #include <stdio.h>
- #include <string.h>
- //User-defined substring function that will take string(str), position(p) and no of character(len) as input.
- //Produces result c as output.
- void substring(char s[], char sub[], int p, int len){
- int c = 0;
- while (c < len) {
- sub[c] = s[p+c];
...
Approach
- Read the string from the user.
- Write the find_substrings() function to get substrings.
- In find_substrings() function call Substring() method to get the substrings.
Approach: It is known for a string of length n, there are a total of n*(n+1)/2 number of substrings.
How to find all the possible substrings of the given string in Java? ›Using Apache Commons Lang Library
As shown above, we used StringUtils. length() to get the length of the original string. Then, we used the StringUtils. substring() method to find all the possible substrings.
No there isn't. It is mathematically impossible. There are O(N^2) substrings of a string of length N . You cannot print O(N^2) strings in O(N) time.
How do you find all occurrences of substring in a string? ›We can also find all occurrences of a substring in a string in python using the finditer() method provided in the re module.
How do you print unique substrings in Python? ›Given a string str and an integer L. The task is to print all the unique substring of length L from string str. Approach: Firstly generate all the substring of length L and then by using set we can insert unique sub-string till the length L and then print the result.
How many different Substrings exist? ›The simplest approach is to generate all possible substrings from the given string and check for each substring whether it contains all distinct characters or not. If the length of string is N, then there will be N*(N+1)/2 possible substrings.
How to count number of occurrences of a character in a string in C#? ›A way to count the occurrence of a character within a string is using the IndexOf() method of the string class.
What substring () and substr () will do? ›The difference between substring() and substr()
The two parameters of substr() are start and length , while for substring() , they are start and end . substr() 's start index will wrap to the end of the string if it is negative, while substring() will clamp it to 0 .
What is the formula for total number of substrings? ›
Total number of substrings = n + (n - 1) + (n - 2) + (n - 3) + (n - 4) + ……. + 2 + 1. So now we have a formula for evaluating the number of substrings where n is the length of a given string.
Which algorithm checks all possible substrings of a given text in finding the pattern? ›The Rabin-Karp string searching algorithm calculates a hash value for the pattern, and for each M-character subsequence of text to be compared.
How to print a substring from a given string in Java? ›- public class TestSubstring{
- public static void main(String args[]){
- String s="SachinTendulkar";
- System.out.println("Original String: " + s);
- System.out.println("Substring starting from index 6: " +s.substring(6));//Tendulkar.
The strstr() function returns pointer to the first occurrence of the matched string in the given string. It is used to return substring from first match till the last character. Syntax: char *strstr(const char *string, const char *match)
How to find substring in Java without using string functions? ›- Take your original string and get a character array ( char[] myChars = myString.toCharArray(); , for example)
- Copy the character array into a new, shorter one ( char[] mySubstringChars = ... )
- Change the shorter char array back into a String ( String mySubstring = new String(mySubstringChars); )
The SUBSTRING() function extracts a substring from a string (starting at any position). Note: The SUBSTR() and MID() functions equals to the SUBSTRING() function.
Which function returns a list of all substrings that match a pattern? ›Just as Python's split() method returns a list of all substrings between whitespace, the regular expression split() method returns a list of all substrings between matches to the input pattern.
How do you find all substrings in Python? ›We can use count() function to find the number of occurrences of a word or a substring in the string. As we are aware with the count function in python.
What is substr () Instr () functions? ›The substr functions allows you to extract a substring from a string. The instr function returns the location of a substring in a string.
How do you retrieve partial matches from a list of strings? ›To find a list of partial query matches given a string list lst , combine the membership operator with the filter() function in which you pass a lambda function that evaluates the membership operation for each element in the list like so: list(filter(lambda x: query in x, lst)) .
What returns how many times a substring occurs in a string? ›
count() method returns an integer that denotes number of times a substring occurs in a given string.
How to find substring in a string in C? ›- Take a string and a substring as input and place them in the corresponding str and sub fields.
- Use the strlen function to determine the length of both strings.
- Determine if a substring is present or not using a for loop. ...
- Print the number of variables as output.
strstr() — Locate Substring
The strstr() function finds the first occurrence of string2 in string1. The function ignores the null character (\0) that ends string2 in the matching process.
The difference between substring() and substr()
The two parameters of substr() are start and length , while for substring() , they are start and end . substr() 's start index will wrap to the end of the string if it is negative, while substring() will clamp it to 0 .
For using Substring, we need to start the function with Left or Right and then select the cells from where we need to get the text, use the LEN function to get the length of characters we want to extract, then subtract the remaining characters using FIND function. By this, we will get Substring.