Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- using namespace std;
- void arr_constructor(string& w, vector<int>& a)
- {
- int i = 2;
- int j = 0;
- a[0] = -1;
- a[1] = 0;
- while (i < w.size())
- {
- if (w[i - 1] == w[j])
- {
- a[i] = j + 1;
- i++;
- j++;
- }
- else if (j > 0)
- j = a[j];
- else
- {
- a[i] = 0;
- i++;
- }
- }
- }
- int solve(string& s, string& w)
- {
- int start = 0;
- int i = 0;
- vector<int> arr;
- arr.assign(w.size() + 2, -1);
- arr_constructor(w, arr);
- while (start + i < s.size())
- {
- if (w[i] == s[i + start])
- {
- i++;
- if (i == w.size())
- return start;
- }
- else
- {
- start = start + i - arr[i];
- if (i > 0)
- i = arr[i];
- }
- }
- return s.size();
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- int z;
- cin >> z;
- while (z--)
- {
- int n;
- string s1;
- string s2;
- cin >> n >> s1 >> s2;
- s1 += s1;
- int result = solve(s1, s2);
- if (result > 0 && result != s1.size())
- cout << "IDENTYCZNE" << endl;
- else
- {
- reverse(s1.begin(), s1.end());
- result = solve(s1, s2);
- if (result > 0 && result != s1.size())
- cout << "IDENTYCZNE" << endl;
- else
- cout << "ROZNE" << endl;
- }
- }
- }
- //01110011
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement