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 functionlong long cyclicPermuationzAlgo(string pattern, string text){text = pattern + "$" + text;long long l = 0, r = 0;vector<long long> z(text.size() + 100, 0);for (long long i = 1; i < text.size(); i++){if (i > r){l = i, r = 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 = 1; i < text.size(); i++){if (pattern.size() == z[i]){ans++;}}return ans;}int main(){string pattern = "101", text = "101";text = text + text.substr(0, text.size() - 1);cout << cyclicPermuationzAlgo(pattern, text) << "\n";return 0;}
No comments:
Post a Comment