Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2016
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6. //Temir Askhat
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define pb push_back
  10. #define sz size()
  11. #define sqr(x) ((x) * (x))
  12. #define mp make_pair
  13. #define F first
  14. #define S second
  15. #define all(c) c.begin(), c.end()
  16. #define rall(c) c.rbegin(), c.rend()
  17. #define tr(container, it) \
  18.  for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  19. #define present(container, element) (container.find(element) != container.end()) // set, map
  20. #define cpresent(container, element) (find(all(container), element) != container.end())\
  21.  
  22.  
  23. vector<int> prefix(string str)  {
  24.     int n = str.size();
  25.     vector<int> p(n);
  26.     int j = 0;
  27.     for(int i = 1; i < n; i++) {
  28.         while(j > 0 && str[i] != str[j])
  29.             j = p[j - 1];
  30.         if(str[i] == str[j]) j++;
  31.         p[i] = j;
  32.     }
  33.     return p;
  34. }
  35.  
  36. int main() {
  37.     #ifndef ONLINE_JUDGE
  38.      freopen("in", "r", stdin); freopen("out", "w", stdout);
  39.     #endif
  40.     int n;
  41.     cin >> n;
  42.     string s, t;
  43.     cin >> s >> t;
  44.     string cur = s + t;
  45.     vector<int> v = prefix(cur);
  46.     while(v[v.sz - 1] != 0) {
  47.         if(v[v.sz - 1] == 0) {
  48.             cout << "NO";
  49.             return 0;
  50.         }
  51.         int end = v[v.sz - 1];
  52.         cur.erase(0, end);
  53.         string current = "";
  54.         //cout << endl;
  55.         for (int i = 0; i < cur.sz - end ; ++i) {
  56.             current += cur[i];
  57.         }
  58.         //cout << "current " << current << endl;
  59.         cur = current;
  60.     //    cout << "cur " << cur << endl;
  61.         if(cur.sz == 0) {
  62.             cout << "YES";
  63.             return 0;
  64.         }
  65.         v = prefix(cur);
  66.     }
  67.     cout << "NO";
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement