# Number of Substrings of One String Present in Other in Java

In this tutorial, we are going to number of substrings of one string present in other in Java. Let's say we have a string s1. We need to determine how many substrings of s1—including multiple instances of the same substring—are contained in string s2.

Examples:

Example 1:

Input: s1 = “cat”, s2 = “concatenation”

Output: 6

Explanation: Substrings of s1 are ["c", "a", "t", "ca","at", "cat"]. These all are present in s2. Hence, the answer is 6.

Example 2:

Input: S1 = "sun", S2 = “sunny day”

Output: 6

Explanation: Substrings of s1 are ["s", "u", "n", "su", "un", "sun"]. These all are present in s2. Hence, the answer is 6.

Example 3:

Input: s1 = "dog", s2 = "dogmatic"

Output: 6

Explanation: Substrings of s1 are ["d", "o", "g", "do", "og", "dog"]. These all are present in s2. Hence, the answer is 6.

Example 4:

Input: s1 = "bird", s2 = "absurdity"

Output: 5

Explanation: Substrings of s1 are ["b", "i", "r", "d", "rd"]. These all are present in s2. Hence, the answer is 5.

Example 5:

Input: s1 = "fish", s2 = "selfish"

Output: 10

Explanation: Substrings of s1 are ["f", "i", "s", "h", "fi", "is", "sh", "fis", "ish","fish"]. These all are present in s2. Hence, the answer is 10.

Example 6:

Input: s1 = "sun", s2 = "sunshine"

Output: 6

Explanation: Substrings of s1 are ["s", "u", "n", "su", "un", "sun"]. These all are present in s2. Hence, the answer is 6.

Example 7:

Input: s1 = "star", s2 = "stardom"

Output: 10

Explanation: Substrings of s1 are ["s", "t", "a", "r", "st", "ta", "ar", "sta", "tar", "star"]. These all are present in s2. Hence, the answer is 10.

` `

## Approach 1: Using brute force

### ALGORITHM:

Step 1: Iterate through every character of s1.

Step 2: Create every conceivable substring that can begin with a given character.

Step 3: Use the indexOf() function to see if each substring is present in s2. In case the substring is located, raise the count.

Step 4: Ultimately, provide the number of substrings discovered in s2.

Filename: NumOfSubString.java

`import java.util.*;public class NumOfSubString{static int countNumberOfSubstrings(String str1, String str2){int result = 0;for (int a = 0; a < str1.length(); a++){            // str1 of all substrings are stored by str3            String str3 = "";            char[] str4 = str1.toCharArray();            for (int b = a; b < str1.length(); b++)            {                        str3 += str4[b];                        // verify whether str2 is present in str3                        if (str2.indexOf(str3) != -1)                                    result++;            }}return result;}public static void main(String[] args){            String str1 = "sun";            String str2 = " sunshine";            System.out.println(countNumberOfSubstrings(str1, str2));}}`

Output:

`6`

Time Complexity: The time complexity of the program is O(n*n).
Space Complexity: The space complexity of the program is O(n).