Advertisement
Guest User

Untitled

a guest
Jan 17th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <math.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <string>
  6. #include <unordered_map>
  7.  
  8.  
  9. const int p = 11;
  10.  
  11.  
  12. long long segment_hash(int l, int r, std::vector<long long> &hash, std::vector<long long> &pow_p) {
  13.     return hash[r] - hash[l - 1] * pow_p[r - l + 1];
  14. }
  15.  
  16.  
  17. int max_palindrom_suffix(std::vector<long long> &hash, std::vector<long long> &rev_hash, std::vector<long long> &pow_p) {
  18.     for (int M = hash.size() - 1; M >= 1; M--) {
  19.         long long hash1 = segment_hash(hash.size() - M, hash.size() - 1, hash, pow_p);
  20.         long long hash2 = segment_hash(1, M, rev_hash, pow_p);
  21.         if (hash1 == hash2)
  22.             return M;
  23.     }
  24. }
  25.  
  26.  
  27. int main() {
  28.     //freopen("input.txt", "r", stdin);
  29.     //freopen("output.txt", "w", stdout);
  30.     int n;
  31.     std::cin >> n;
  32.     std::vector<long long> pow_p(n + 1, 1);
  33.     for (int i = 1; i < n + 1; i++) {
  34.         pow_p[i] = pow_p[i - 1] * p;
  35.     }
  36.     std::string s;
  37.     int x;
  38.     for (int i = 0; i < n; i++) {
  39.         std::cin >> x;
  40.         s += '0' + x;
  41.     }
  42.     std::vector<long long> hash(n + 1);
  43.     std::vector<long long> rev_hash(n + 1);
  44.     for (int i = 1; i < n + 1; i++) {
  45.         hash[i] = hash[i - 1] * p + (s[i - 1] - '0');
  46.         rev_hash[i] = rev_hash[i - 1] * p + (s[n - i] - '0');
  47.     }
  48.     int length = max_palindrom_suffix(hash, rev_hash, pow_p);
  49.     //std::cout << length;
  50.     //std::cout << segment_hash(1, 2, hash, pow_p);
  51.     //std::cout << segment_hash(3, 4, hash, pow_p);
  52.     std::cout << n - length << "\n";
  53.     for (int i = n - length - 1; i >= 0; i--) {
  54.         std::cout << s[i] << ' ';
  55.     }
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement