Cyclic Permutations

Given two binary strings A and B, count how many cyclic permutations of B when taken XOR with A give 0.

Example:

Input:  pattern = "101", text = "101";
Output: 1

Approach

C++

#include <bits/stdc++.h>
using namespace std;

//Z function
long long cyclicPermuationzAlgo(string patternstring text)
{
    text = pattern + "$" + text;
    long long l = 0r = 0;
    vector<long longz(text.size() + 1000);
    for (long long i = 1i < text.size(); i++)
    {
        if (i > r)
        {
            l = ir = i;
            while (r < text.size() && text[r] == text[r - l])
            {
                r++;
            }
            z[i] = r - l;
            r--;
        }
        else
        {
            if (z[i - l] < (r - i + 1))
            {
                z[i] = z[i - l];
            }
            else
            {
                l = i;
                while (r < text.size() && text[r - l] == text[r])
                {
                    r++;
                }
                z[i] = r - l;
                r--;
            }
        }
    }

    long long ans = 0;
    for (int i = 1i < text.size(); i++)
    {
        if (pattern.size() == z[i])
        {
            ans++;
        }
    }
    return ans;
}

int main()
{

    string pattern = "101"text = "101";

    text = text + text.substr(0text.size() - 1);
    cout << cyclicPermuationzAlgo(patterntext<< "\n";

    return 0;
}


No comments:

Post a Comment