import java.util.Scanner;
class SubstringsOfAString
{
public static void main(String args[])
{
String string, sub;
int i, c, length;
Scanner in = new Scanner(System.in);
System.out.println("Enter a string to print it's all substrings");
string = in.nextLine();
length = string.length();
System.out.println("Substrings of ""+string+"" are :-");
for( c = 0 ; c < length ; c++ )
{
for( i = 1 ; i <= length - c ; i++ )
{
sub = string.substring(c, c+i);
System.out.println(sub);
}
}
}
}
Step-by-Step Explanation:
1. Import Scanner Class:
import java.util.Scanner;
– The Scanner class is imported to permit input from the user through the console.
2. Class Definition:
class SubstringsOfAString
– A class called SubstringsOfAString is defined. In the class lies the main method that represents where a Java program will begin execution from.
3. Main Method:
public static void main(String args[])
– The main method is where the program begins. Run time starts from here.
4. Variable Declarations:
String string, sub;
int i, c, length;
– string: This will hold the input string provided by the user.
– sub: This holds the current substring being constructed.
– i and c: Loop variables used to control the nested loops.
– length: This stores the length of the input string.
5. Creating a Scanner Object to Read Input:
Scanner in = new Scanner(System.in);
System.out.println(“Enter a string to print it’s all substrings”);
string = in.nextLine();
– A Scanner object in is declared which reads input for the user.
– The program requires the user to write a string, while this string, in turn is stored in the string variable.
6. Getting the Length of the String:
– The length() method of the String class is used to get the length of the input string. This value is stored in the variable length.
7. Printing the Header:
System.out.println(“Substrings of “” + string + “” are :-“);
– The program prints a message saying that it will print all substrings of the input string.
8. Generating and Printing Substrings:
for (c = 0; c < length; c++)
{
for (i = 1; i <= length – c; i++)
{
sub = string.substring(c, c + i);
System.out.println(sub);
}
}
– Outer loop, “for (c = 0; c < length; c++)”: Control start position for substrings. c denotes the start position of a substring
c initializes to 0, meaning starting at the first character of the string and iterates upward until reaching the last character in the string.
– The inner loop for (i = 1; i <= length – c; i++) is used to control the length of the substrings.
For each value of c, the inner loop generates substrings starting from index c and extends the substring by increasing the value of i that determines the length of the substring.
– substring(c, c + i) returns the String subclass method: returns a string containing a subset of characters between indices c and c+i.
– Store every generated substring into the variable sub, print them all out with System.out.println(sub);
9. End
– After the loops, all substrings of the input string are printed and the program terminates.
Example Walkthrough:
Suppose the user gives the string as “abc”.
Sample Input:
Enter a string to print it’s all substrings
abc
Output:
Substrings of “abc” are :-
a
ab
abc
b
bc
c
Explanation of Output:
– Starting with “a”: The outer loop begins at c = 0. The inner loop creates substrings of length n starting from index 0:
– substring(0, 1) → “a”
– substring(0, 2) → “ab”
– substring(0, 3) → “abc”
.
– Starting with “b”: The outer loop shifts to c = 1. The inner loop creates substrings starting from index 1:
– substring(1, 2) → “b”
– substring(1, 3) → “bc”
– With “c” as the first: The outer loop shifts to c = 2. The inner loop produces one substring from index 2:
– substring(2, 3) → “c”
So, all substrings are printed in the following order:
a
ab
abc
b
bc
c
The program basically uses two nested loops to form the substrings. The outer loop runs in n time, where n is the string length. For each of the outer loop iterations, in turn, the inner loop runs for up to n times. So, in total, there would be approximately (frac{n(n+1)}{2}) execution times, which makes it time complexity of O(n^2).
Space Complexity:
– The space complexity is (O(1)), as only a few variables are used to store the string, the current substring, and loop counters. The substrings themselves are printed immediately and not stored in memory, so the space required does not grow with the input size.
Conclusion:
This program creates and prints all substrings possible with a given string. It systematically extracts each substring and prints it by the use of two nested loops. All substrings starting from each character of the input, with increasing lengths, are outputted.