Number of substrings of one string present in other
Last Updated :
07 Oct, 2022
Suppose we are given a string s1, we need to the find total number of substring(including multiple occurrences of the same substring) of s1 which are present in string s2.
Examples:
Input : s1 = aab
s2 = aaaab
Output :6
Substrings of s1 are ["a", "a", "b", "aa",
"ab", "aab"]. These all are present in s2.
Hence, answer is 6.
Input :s1 = abcd
s2 = swalencud
Output :3
The idea is to consider all substrings of s1 and check if it present in s2.
Implementation:
C++
#include<iostream>
#include<string>
using namespace std;
int countSubstrs(string s1, string s2)
{
int ans = 0;
for (int i = 0; i < s1.length(); i++) {
string s3;
for (int j = i; j < s1.length(); j++) {
s3 += s1[j];
if (s2.find(s3) != string::npos)
ans++;
}
}
return ans;
}
int main()
{
string s1 = "aab", s2 = "aaaab";
cout << countSubstrs(s1, s2);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static int countSubstrs(String s1,
String s2)
{
int ans = 0;
for (int i = 0; i < s1.length(); i++)
{
String s3 = "";
char[] s4 = s1.toCharArray();
for (int j = i; j < s1.length(); j++)
{
s3 += s4[j];
if (s2.indexOf(s3) != -1)
ans++;
}
}
return ans;
}
public static void main(String[] args)
{
String s1 = "aab", s2 = "aaaab";
System.out.println(countSubstrs(s1, s2));
}
}
|
Python 3
def countSubstrs(s1, s2) :
ans = 0
for i in range(len(s1)) :
s3 = ""
for j in range(i, len(s1)) :
s3 += s1[j]
if s2.find(s3) != -1 :
ans += 1
return ans
if __name__ == "__main__" :
s1 = "aab"
s2 = "aaaab"
print(countSubstrs(s1, s2))
|
C#
using System;
class GFG
{
static int countSubstrs(String s1,
String s2)
{
int ans = 0;
for (int i = 0; i < s1.Length; i++)
{
String s3 = "";
char[] s4 = s1.ToCharArray();
for (int j = i; j < s1.Length; j++)
{
s3 += s4[j];
if (s2.IndexOf(s3) != -1)
ans++;
}
}
return ans;
}
public static void Main(String[] args)
{
String s1 = "aab", s2 = "aaaab";
Console.WriteLine(countSubstrs(s1, s2));
}
}
|
PHP
<?php
function countSubstrs($s1, $s2)
{
$ans = 0;
for ($i = 0; $i < strlen($s1); $i++)
{
$s3 = "";
for ($j = $i;
$j < strlen($s1); $j++)
{
$s3 += $s1[$j];
if (stripos($s2, $s3, 0) != -1)
$ans++;
}
}
return $ans;
}
$s1 = "aab";
$s2 = "aaaab";
echo countSubstrs($s1, $s2);
?>
|
Javascript
<script>
function countSubstrs( s1, s2)
{
var ans = 0;
for (var i = 0; i < s1.length; i++)
{
var s3 = "";
var s4 = s1 ;
for (var j = i; j < s1.length; j++)
{
s3 += s4[j];
if (s2.indexOf(s3) != -1)
ans++;
}
}
return ans;
}
var s1 = "aab", s2 = "aaaab";
document.write(countSubstrs(s1, s2));
</script>
|
Complexity Analysis:
- Time Complexity: O(n*n*n), as nested loops are used where n is the size of string s1
- Auxiliary Space: O(n), as extra space for string s3 is being used
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...