test

Here’s the C++ implementation along with the example you provided:

---

C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxMatchingPairs(vector<int>& a, vector<int>& b) {
    int n = a.size();
    vector<int> position(n + 1, 0);
    vector<int> shift_count(n, 0);

    // Step 1: Create position array for b
    for (int i = 0; i < n; ++i) {
        position[b[i]] = i;
    }

    // Step 2: Calculate shift counts
    for (int i = 0; i < n; ++i) {
        int k = (position[a[i]] - i + n) % n; // Calculate the shift needed
        shift_count[k]++;
    }

    // Step 3: Find the maximum shift count
    return *max_element(shift_count.begin(), shift_count.end());
}

int main() {
    // Example
    vector<int> a = {1, 3, 2, 4};
    vector<int> b = {4, 2, 3, 1};

    cout << "Maximum matching pairs: " << maxMatchingPairs(a, b) << endl;

    return 0;
}

---

Example Walkthrough:

Input:

• a=[1,3,2,4]a = [1, 3, 2, 4]
• b=[4,2,3,1]b = [4, 2, 3, 1]

Steps:

1. Create position Array for bb: position=[0,3,1,2,0]position = [0, 3, 1, 2, 0] (Index of 1=31 = 3, 2=12 = 1, 3=23 = 2, 4=04 = 0).
2. Calculate Shifts kk:
   For each ii:
   • i=0,a[0]=1i = 0, a[0] = 1:
     k=(position[1]−0+4)%4=(3−0+4)%4=3k = (position[1] – 0 + 4) \% 4 = (3 – 0 + 4) \% 4 = 3
   • i=1,a[1]=3i = 1, a[1] = 3:
     k=(position[3]−1+4)%4=(2−1+4)%4=1k = (position[3] – 1 + 4) \% 4 = (2 – 1 + 4) \% 4 = 1
   • i=2,a[2]=2i = 2, a[2] = 2:
     k=(position[2]−2+4)%4=(1−2+4)%4=3k = (position[2] – 2 + 4) \% 4 = (1 – 2 + 4) \% 4 = 3
   • i=3,a[3]=4i = 3, a[3] = 4:
     k=(position[4]−3+4)%4=(0−3+4)%4=1k = (position[4] – 3 + 4) \% 4 = (0 – 3 + 4) \% 4 = 1
   Resulting shift_count: shift_count=[0,2,0,2]shift\_count = [0, 2, 0, 2]
3. Find Maximum Matches:
   Maximum value in shift_count is 22.

Output:

Maximum matching pairs: 2

---

Explanation:

The optimal cyclic shift is either k=1k = 1 or k=3k = 3, which gives 2 matching pairs in both cases.