Program to print all substrings of a given string
Last Updated :
08 Dec, 2023
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++
#include<bits/stdc++.h>
using namespace std;
void subString(char str[], int n)
{
for (int len = 1; len <= n; len++)
{
for (int i = 0; i <= n - len; i++)
{
int j = i + len - 1;
for (int k = i; k <= j; k++)
cout << str[k];
cout << endl;
}
}
}
int main()
{
char str[] = "abc";
subString(str, strlen(str));
return 0;
}
|
Java
class GFG {
static void subString(char str[], int n) {
for (int len = 1; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
for (int k = i; k <= j; k++) {
System.out.print(str[k]);
}
System.out.println();
}
}
}
public static void main(String[] args) {
char str[] = {'a', 'b', 'c'};
subString(str, str.length);
}
}
|
Python
def subString(Str,n):
for Len in range(1,n + 1):
for i in range(n - Len + 1):
j = i + Len - 1
for k in range(i,j + 1):
print(Str[k],end="")
print()
Str = "abc"
subString(Str,len(Str))
|
C#
using System;
public class GFG {
static void subString(string str,
int n)
{
for (int len = 1; len <= n;
len++)
{
for (int i = 0;
i <= n - len; i++)
{
int j = i + len - 1;
for (int k = i; k <= j;
k++)
Console.Write(str[k]);
Console.WriteLine();
}
}
}
static public void Main ()
{
string str = "abc";
subString(str, str.Length);
}
}
|
Javascript
<script>
function subString(str,n)
{
for (let len = 1; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
let j = i + len - 1;
for (let k = i; k <= j; k++) {
document.write(str[k]);
}
document.write("<br>");
}
}
}
let str=['a', 'b', 'c'];
subString(str, str.length);
</script>
|
PHP
<?php
function subString($str, $n)
{
for ($len = 1; $len <= $n; $len++)
{
for ($i = 0; $i <= $n - $len; $i++)
{
$j = $i + $len - 1;
for ($k = $i; $k <= $j; $k++)
echo $str[$k];
echo "\n";
}
}
}
$str = "abc";
subString($str, strlen($str));
?>
|
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++
#include<bits/stdc++.h>
using namespace std;
void subString(string s, int n)
{
for (int i = 0; i < n; i++)
for (int len = 1; len <= n - i; len++)
cout << s.substr(i, len) << endl;
}
int main()
{
string s = "abcd";
subString(s,s.length());
return 0;
}
|
Java
public class GFG {
public static void SubString(String str, int n)
{
for (int i = 0; i < n; i++)
for (int j = i+1; j <= n; j++)
System.out.println(str.substring(i, j));
}
public static void main(String[] args)
{
String str = "abcd";
SubString(str, str.length());
}
}
|
Python3
def subString(s, n):
for i in range(n):
for len in range(i+1,n+1):
print(s[i: len]);
s = "abcd";
subString(s,len(s));
|
C#
using System;
public class GFG {
public static void SubString(String str, int n)
{
for (int i = 0; i < n; i++)
for (int j = 1; j <= n - i; j++)
Console.WriteLine(str.Substring(i, j));
}
public static void Main()
{
String str = "abcd";
SubString(str, str.Length);
}
}
|
Javascript
<script>
function SubString( str , n)
{
for (var i = 0; i < n; i++)
for (var j = i+1; j <= n; j++)
document.write(str.substring(i, j)+"<br/>");
}
var str = "abcd";
SubString(str, str.length);
</script>
|
PHP
<?php
function subString($s, $n) {
for ($i = 0; $i < $n; $i++) {
for ($len = $i + 1; $len <= $n; $len++) {
echo substr($s, $i, $len - $i) . "\n";
}
}
}
$s = "abcd";
subString($s, strlen($s));
?>
|
Output
a
ab
abc
abcd
b
bc
bcd
c
cd
d
Time complexity: O( n^3 )
Auxiliary Space: O(1)
Method 3 (Generate a substring using the previous substring):
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
void printAllSubstrings(string s, int n)
{
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);
}
}
}
int main()
{
string s = "Geeky";
printAllSubstrings(s, s.length());
return 0;
}
|
Java
import java.io.*;
class GFG{
public static void printAllSubStrings(String s,
int n)
{
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);
}
}
}
public static void main(String[] args)
{
String s = "Geeky";
printAllSubStrings(s, s.length());
}
}
|
Python3
def printAllSubstrings(s, n):
for i in range(n):
temp=""
for j in range(i,n):
temp+=s[j]
print(temp)
s = "Geeky"
printAllSubstrings(s, len(s))
|
C#
using System;
class GFG{
public static void printAllSubStrings(String s, int n)
{
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);
}
}
}
public static void Main()
{
String s = "Geeky";
printAllSubStrings(s, s.Length);
}
}
|
Javascript
<script>
function printAllSubStrings(s, n)
{
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>
|
PHP
<?php
function printAllSubstrings($s, $n) {
for ($i = 0; $i < $n; $i++) {
$temp = "";
for ($j = $i; $j < $n; $j++) {
$temp .= $s[$j];
echo $temp . "\n";
}
}
}
$s = "Geeky";
printAllSubstrings($s, strlen($s));
?>
|
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++
#include <iostream>
using namespace std;
void printSubstrings(string str)
{
int n = str.length();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
cout << str[k];
}
cout << endl;
}
}
}
int main()
{
string str = "abcd";
printSubstrings(str);
return 0;
}
|
C
#include <stdio.h>
void printSubstrings(char str[])
{
for (int start = 0; str[start] != '\0'; start++) {
for (int end = start; str[end] != '\0'; end++) {
for (int i = start; i <= end; i++) {
printf("%c", str[i]);
}
printf("\n");
}
}
}
int main()
{
char str[] = { 'a', 'b', 'c', 'd', '\0' };
printSubstrings(str);
return 0;
}
|
Java
import java.io.*;
class GFG {
public static void printSubstrings(String str)
{
int n = str.length();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
System.out.print(str.charAt(k));
}
System.out.println();
}
}
}
public static void main(String[] args)
{
String str = "abcd";
printSubstrings(str);
}
}
|
Python3
def printSubstrings(string, n):
for i in range(n):
for j in range(i, n):
for k in range(i, (j + 1)):
print(string[k], end="")
print()
string = "abcd"
printSubstrings(string, len(string))
|
C#
using System;
public class GFG {
public static void printSubstrings(String str)
{
int n = str.Length;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++) {
Console.Write(str[k]);
}
Console.WriteLine();
}
}
}
public static void Main(String[] args)
{
String str = "abcd";
printSubstrings(str);
}
}
|
Javascript
<script>
function printSubstrings(str)
{
var n = str.length;
for (var i = 0; i < n; i++) {
for (var j = i; j < n; j++) {
for (var k = i; k <= j; k++) {
document.write(str.charAt(k));
}
document.write("<br>");
}
}
}
var str = "abcd";
printSubstrings(str);
</script>
|
PHP
<?php
function printSubstrings($string, $n) {
for ($i = 0; $i < $n; $i++) {
for ($j = $i; $j < $n; $j++) {
for ($k = $i; $k <= $j; $k++) {
echo $string[$k];
}
echo "\n";
}
}
}
$string = "abcd";
printSubstrings($string, strlen($string));
?>
|
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++
#include <iostream>
using namespace std;
void printSubstrings(string str)
{
for (int i = 0; i < str.length(); i++) {
string subStr;
for (int j = i; j < str.length(); j++) {
subStr += str[j];
cout << subStr << endl;
}
}
}
int main()
{
string str = "abcd";
printSubstrings(str);
return 0;
}
|
Java
import java.util.*;
class GFG{
static void printSubStrings(String str)
{
for (int i = 0; i < str.length(); i++) {
String subStr="";
for (int j = i; j < str.length(); j++) {
subStr += str.charAt(j);
System.out.print(subStr +"\n");
}
}
}
public static void main(String[] args)
{
String str = "abcd";
printSubStrings(str);
}
}
|
Python3
def printSubStrings(str):
for i in range(len(str)):
subStr = ""
for j in range(i,len(str)):
subStr += str[j]
print(subStr + "")
if __name__ == '__main__':
str = "abcd"
printSubStrings(str)
|
C#
using System;
public class GFG{
static void printSubStrings(String str)
{
for (int i = 0; i < str.Length; i++) {
String subStr="";
for (int j = i; j < str.Length; j++) {
subStr += str[j];
Console.Write(subStr +"\n");
}
}
}
public static void Main(String[] args)
{
String str = "abcd";
printSubStrings(str);
}
}
|
Javascript
<script>
function printSubStrings( str) {
for (i = 0; i < str.length; i++) {
var subStr = "";
for (var j = i; j < str.length; j++) {
subStr += str.charAt(j);
document.write(subStr + "<br/>");
}
}
}
var str = "abcd";
printSubStrings(str);
</script>
|
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.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...