Given 2 strings A and B, the task is to count the number of substrings of A which are also present in B.
Example:
Input: a="plu" b="Cplusplus" Output: 6 Explanation: p, l, u, pl, lu, and plu are the 6 substrings of string a present in string b also.
Approach:
We will just run 2 loops and find every substring of string a and check if it’s present in string b or not.
Implementation in C++:
#include <bits/stdc++.h>
using namespace std;
int count(string a, string b)
{
int count=0;
int n=a.size();
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n-i;j++)
{
string str=a.substr(j,i);
int pos=b.find(str);
if(pos!=-1)
count++;
}
}
return count;
}
int main()
{
string a="plu", b="Cplusplus";
cout<<count(a,b);
return 0;
}
Output:
6
Time Complexity: O(n*n) = O(n^2)
