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)