Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <math.h>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <unordered_map>
- const int p = 11;
- long long segment_hash(int l, int r, std::vector<long long> &hash, std::vector<long long> &pow_p) {
- return hash[r] - hash[l - 1] * pow_p[r - l + 1];
- }
- int max_palindrom_suffix(std::vector<long long> &hash, std::vector<long long> &rev_hash, std::vector<long long> &pow_p) {
- for (int M = hash.size() - 1; M >= 1; M--) {
- long long hash1 = segment_hash(hash.size() - M, hash.size() - 1, hash, pow_p);
- long long hash2 = segment_hash(1, M, rev_hash, pow_p);
- if (hash1 == hash2)
- return M;
- }
- }
- int main() {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int n;
- std::cin >> n;
- std::vector<long long> pow_p(n + 1, 1);
- for (int i = 1; i < n + 1; i++) {
- pow_p[i] = pow_p[i - 1] * p;
- }
- std::string s;
- int x;
- for (int i = 0; i < n; i++) {
- std::cin >> x;
- s += '0' + x;
- }
- std::vector<long long> hash(n + 1);
- std::vector<long long> rev_hash(n + 1);
- for (int i = 1; i < n + 1; i++) {
- hash[i] = hash[i - 1] * p + (s[i - 1] - '0');
- rev_hash[i] = rev_hash[i - 1] * p + (s[n - i] - '0');
- }
- int length = max_palindrom_suffix(hash, rev_hash, pow_p);
- //std::cout << length;
- //std::cout << segment_hash(1, 2, hash, pow_p);
- //std::cout << segment_hash(3, 4, hash, pow_p);
- std::cout << n - length << "\n";
- for (int i = n - length - 1; i >= 0; i--) {
- std::cout << s[i] << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement