Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void arr_constructor(string& w, vector<int>& a)
  9. {
  10.     int i = 2;
  11.     int j = 0;
  12.  
  13.     a[0] = -1;
  14.     a[1] = 0;
  15.  
  16.     while (i < w.size())
  17.     {
  18.         if (w[i - 1] == w[j])
  19.         {
  20.             a[i] = j + 1;
  21.             i++;
  22.             j++;
  23.         }
  24.         else if (j > 0)
  25.             j = a[j];
  26.         else
  27.         {
  28.             a[i] = 0;
  29.             i++;
  30.         }
  31.     }
  32. }
  33.  
  34. int solve(string& s, string& w)
  35. {
  36.     int start = 0;
  37.     int i = 0;
  38.     vector<int> arr;
  39.  
  40.     arr.assign(w.size() + 2, -1);
  41.     arr_constructor(w, arr);
  42.  
  43.     while (start + i < s.size())
  44.     {
  45.         if (w[i] == s[i + start])
  46.         {
  47.             i++;
  48.  
  49.             if (i == w.size())
  50.                 return start;
  51.         }
  52.         else
  53.         {
  54.             start = start + i - arr[i];
  55.  
  56.             if (i > 0)
  57.                 i = arr[i];
  58.         }
  59.     }
  60.  
  61.     return s.size();
  62. }
  63.  
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(false);
  67.  
  68.     int z;
  69.  
  70.     cin >> z;
  71.  
  72.     while (z--)
  73.     {
  74.         int n;
  75.         string s1;
  76.         string s2;
  77.  
  78.         cin >>  n >> s1 >> s2;
  79.  
  80.         s1 += s1;
  81.  
  82.         int result = solve(s1, s2);
  83.  
  84.         if (result > 0 && result != s1.size())
  85.             cout << "IDENTYCZNE" << endl;
  86.         else
  87.         {
  88.             reverse(s1.begin(), s1.end());
  89.  
  90.             result = solve(s1, s2);
  91.  
  92.             if (result > 0 && result != s1.size())
  93.                 cout << "IDENTYCZNE" << endl;
  94.             else
  95.                 cout << "ROZNE" << endl;
  96.         }  
  97.     }
  98. }
  99.  
  100.  
  101.  
  102.  
  103. //01110011
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement