Count of common subarrays in two different permutations of 1 to N | C ++ implementation of above approach ; Initialising Map for Index Mapping ; Mapping elements of A ; Modify elements of B according to Map ; Changing B [ i ] as the index of B [ i ] in A ; Count of common subarrays ; Traversing array B ; While consecutive elements are found , we increment K ; Add number of subarrays with length K to total count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int commonSubarrays ( int * A , int * B , int N ) { int Map [ N + 1 ] ; for ( int i = 0 ; i < N ; i ++ ) Map [ * ( A + i ) ] = i ; for ( int i = 0 ; i < N ; i ++ ) { * ( B + i ) = Map [ * ( B + i ) ] ; } int count = 0 ; int i = 0 , K ; while ( i < N ) { K = 1 ; i += 1 ; while ( i < N && B [ i ] == B [ i - 1 ] + 1 ) { i += 1 ; K += 1 ; } count = count + ( ( K ) * ( K + 1 ) ) / 2 ; } return count ; } int main ( ) { int N = 3 ; int A [ ] = { 1 , 2 , 3 } ; int B [ ] = { 2 , 3 , 1 } ; cout << ( commonSubarrays ( A , B , N ) ) << endl ; N = 5 ; int C [ ] = { 1 , 2 , 3 , 4 , 5 } ; int D [ ] = { 2 , 3 , 1 , 4 , 5 } ; cout << ( commonSubarrays ( C , D , N ) ) ; }