# 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: NumOf****SubString.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).