Efficient Approach
Prerequisite: KMP Algorithm
Let us look at this problem in another way. We have to check if B exists as a subarray of A or not, but the extra thing is that we can add any value to all B elements. This means that array B is not fixed. Can we try to figure out something that remains constant in the whole process? The difference between consecutive elements.
The difference between consecutive elements of both A and B is the same. If we replace A and B by the difference of their consecutive elements, we will have to check the number of times array B appears as a subarray in A. We can use various string matching algorithms like KMP, Z-algorithm, Rabin Karp to solve this efficiently.
Implementation using KMP
#include <bits/stdc++.h>
using namespace std;
vector<int> getLps(int m, int b[]){
// Vector to store the LPS array.
vector<int>lps(m);
/*
Prev is the last longest proper prefix
which is also a suffix
*/
int prev = 0;
int ind = 1;
while (ind < m){
// If both are equal
if (b[ind]==b[prev]){
prev++;
lps[ind]=prev;
ind++;
}
/*
If the current elements are unequal
And LPS is 0
*/
else if (prev==0){
lps[ind]=0;
ind++;
}
/*
If the current elements are unequal
But LPS is not 0
*/
else{
prev = lps[prev-1];
}
}
return lps;
}
// Function to implement KMP
int kmp(int n, int m, int a[], int b[]){
vector<int> lps = getLps(m, b);
// Initializing variables
int ans = 0;
int aIdx = 0;
int bIdx = 0;
while (bIdx < n){
// If both the elements match
if (a[bIdx] == b[aIdx]){
aIdx++;
bIdx++;
}
if (aIdx == m){
// This means that the entire pattern has matched
ans++;
// Updating aIdx to the last element matched.
aIdx = lps[aIdx-1];
}
else if (bIdx < n){
if (a[bIdx]!=b[aIdx]){
if (aIdx != 0)
// Updating lps to the last element matched
aIdx = lps[aIdx-1];
else
// If no element matched, we move to next index
bIdx++;
}
}
}
return ans;
}
// Number of times array B appears as a subarray in A
void solve(int n, int m, int a[], int b[]){
int difa[n-1];
int difb[m-1];
// Storing difference of consecutive elements
for(int i=0; i<n-1; i++){
difa[i] = a[i+1]-a[i];
}
for(int i=0; i<m-1; i++){
difb[i] = b[i+1]-b[i];
}
/*
Using KMP to find the
Number of times array B appears as a subarray in A
*/
int ans = kmp(n-1, m-1, difa, difb);
cout<<ans<<endl;
}
// Driver Code
int main(){
int N = 10, M = 5;
int A[] = {5, 10, 8, 10, 11, 9, 11, 12, 10, 15};
int B[] = {4, 2, 4, 5, 3};
solve(N, M, A, B);
}
Output
2
Implementation using Z-Algorithm
Prerequisite: Z-algorithm
The Z array for any array ‘Arr’ of length 'N' is an array of size 'N' where the ith element is equal to the maximum number of elements starting from the position ‘i’ that coincide with the starting elements of ‘Arr’. To solve this problem, we can create a Z array of ‘B’ + [some random number] + ‘A’. Now, whenever Z[i] is equal to ‘M’ (the length of B), we will increment our answer by 1 as it will mean the starting ‘M’ characters (which is actually the array B) have matched.
#include <bits/stdc++.h>
using namespace std;
#include<iostream>
using namespace std;
// Fills Z array for given array
void getZarr(int n, int a[], int Z[])
{
int left, right, k;
// [left,right] make a window which matches with prefix of s
left = right = 0;
for (int i = 1; i < n; ++i)
{
// if i>right nothing matches so we will calculate.
// Z[i] using a naive way.
if (i > right)
{
left = right = i;
while (right<n && a[right-left] == a[right])
right++;
Z[i] = right-left;
right--;
}
else
{
// k = i-left so k corresponds to number which
// matches in [left,right] interval.
k = i-left;
if (Z[k] < right-i+1)
Z[i] = Z[k];
// For example a = "aaaaaa" and i = 2, right is 5,
// left is 0
else
{
// else start from right and check manually
left = i;
while (right<n && a[right-left] == a[right])
right++;
Z[i] = right-left;
right--;
}
}
}
}
// Function to implement Z-Algo
int ZAlgo(int n, int m, int a[], int b[])
{
// Create concatenated array
int concat[n+m+1];
for(int i=0; i<m; i++){
concat[i] = b[i];
}
concat[m] = -1000000;
for(int i=m+1; i<n+m+1; i++){
concat[i] = a[i-m-1];
}
int l = n+m+1;
// Construct Z array
int Z[l];
getZarr(l, concat, Z);
int ans = 0;
// now looping through Z array for matching condition
for (int i = 0; i < l; ++i)
{
// if Z[i] is equal to length of b
if (Z[i] == m) ans++;
}
return ans;
}
// Number of times array B appears as a subarray in A
void solve(int n, int m, int a[], int b[]){
int difa[n-1];
int difb[m-1];
// Storing difference of consecutive elements
for(int i=0; i<n-1; i++){
difa[i] = a[i+1]-a[i];
}
for(int i=0; i<m-1; i++){
difb[i] = b[i+1]-b[i];
}
/*
Using KMP to find the
Number of times array B appears as a subarray in A
*/
int ans = ZAlgo(n-1, m-1, difa, difb);
cout<<ans<<endl;
}
// Driver Code
int main(){
int N = 10, M = 5;
int A[] = {5, 10, 8, 10, 11, 9, 11, 12, 10, 15};
int B[] = {4, 2, 4, 5, 3};
solve(N, M, A, B);
}
Output
2
Time Complexity: O(N + M)
Both KMP and Z-Algorithm take linear time to find the number of times array B appears as a subarray in A. Therefore, the time complexity of the above approach is O(N + M).
Space Complexity: O(N+M)
We have created two new arrays to store consecutive elements of A and B. This will take O(N + M) space. KMP and Z-Algorithm also use linear space. Therefore the total space complexity is O(N + M).
FAQs
-
What is the use of the KMP algorithm?
The KMP algorithm is used to find patterns in long strings. It can be used to search a substring in a string, find the number of unique substrings in a string, find all occurrences of the pattern in the string, etc.
-
What are other similar algorithms?
Z Algorithm also searches for the given pattern in the string. Both these algorithms have the same space and time complexity, but the Z algorithm is simpler to understand. There is another algorithm called Rabin Karp, which uses O(1) space.
-
What is the LPS array?
LPS stands for Longest proper Prefix, which is also a Suffix. As the name suggests, LPS[i] stores the longest proper prefix and a substring pat suffix [0:i]. A string’s proper prefix is any other than the entire string itself.
Key Takeaways
In this article, we discussed the approach to finding the number of times array B appears as a subarray in A, given that we can add any constant value to all elements of B. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.
If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.
Check out this problem - Subarray With 0 Sum
Until then, All the best for your future endeavors, and Keep Coding.
24+ registered 
