Advertisement
Guest User

Untitled

a guest
Jul 24th, 2014
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.16 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _SCL_SECURE_NO_WARNINGS
  3. //#define _CRT_RAND_S
  4.  
  5. //#include <windows.h>
  6. //#include <tchar.h>
  7. //#include <atlbase.h>
  8. //#include <winerror.h>
  9.  
  10. //#define BOOST_FILESYSTEM_NO_DEPRECATED
  11. //#include <boost/filesystem.hpp>
  12. //#include <boost/filesystem/fstream.hpp>
  13. //#include <boost/regex.hpp>
  14. //#include <boost/algorithm/string.hpp>
  15.  
  16. #include <stdint.h>
  17. #include <climits>
  18. #include <ctime>
  19. #include <cmath>
  20. #include <cstdio>
  21. #include <cstdlib>
  22. #include <cstring>
  23.  
  24. #include <map>
  25. #include <set>
  26. #include <list>
  27. #include <queue>
  28. #include <deque>
  29. #include <string>
  30. #include <bitset>
  31. #include <vector>
  32. #include <iostream>
  33. #include <algorithm>
  34.  
  35. //#include <unordered_set>
  36. //#include <unordered_map>
  37.  
  38. using namespace std;
  39. //using namespace tr1;
  40.  
  41. typedef unsigned int uint;
  42. typedef long long ll;
  43. typedef unsigned long long ull;
  44. typedef pair<int, int> pii;
  45. typedef pair<ll, int> pli;
  46. typedef pair<ll, ll> pll;
  47.  
  48. //#include <gmpxx.h>
  49. //typedef mpz_class mpz;
  50. //typedef mpq_class mpq;
  51. //typedef mpf_class mpf;
  52. //typedef pair<mpz, mpz> pzz;
  53.  
  54. //mpz int64_to_mpz(int64_t x) { return (mpz(int32_t(x >> 32)) << 32) | mpz(uint32_t(x & 0xFFFFFFFF)); }
  55. //int64_t mpz_to_int64(mpz x) { mpz xh = x >> 32, xl = x & 0xFFFFFFFF; return (int64_t(xh.get_si()) << 32) | uint64_t(xl.get_ui()); }
  56. //int64_t mulmod(int64_t x, int64_t y, int64_t m) { return mpz_to_int64((int64_to_mpz(x) * int64_to_mpz(y)) % int64_to_mpz(m)); }
  57. //int is_prime(int64_t x, int iter = 8) { return mpz_probab_prime_p(int64_to_mpz(x).get_mpz_t(), iter); }
  58. //int64_t next_prime(int64_t x) { mpz p; mpz_nextprime(p.get_mpz_t(), int64_to_mpz(x).get_mpz_t()); return mpz_to_int64(p); }
  59. //int64_t cb(int32_t x) { return int64_t(x)*x*x; }
  60. //int32_t icbrt(int64_t x) { int32_t q = int32_t(pow(double(x), 1.0/3)); while (cb(q) > x) q--; while (cb(q+1) <= x) q++; return q; }
  61. int64_t isq(int32_t x) { return int64_t(x)*x; }
  62. int64_t isq(int64_t x) { return int64_t(x)*x; }
  63. int32_t isqrt(int64_t x) { if (x <= 0) return 0; int32_t q = int32_t(floor(sqrt(double(x)))); while (isq(q) > x) q--; while (isq(q+1) <= x) q++; return q; }
  64. //int32_t isqrtc(int64_t x) { if (x <= 0) return 0; int32_t q = int32_t(ceil(sqrt(double(x)))); while (isq(q) < x) q++; while (q > 0 && isq(q-1) >= x) q--; return q; }
  65. //int is_square(int64_t x) { return (isq(isqrt(x)) == x); }
  66. int64_t div_floor(int64_t a, int64_t b) { if (b < 0) a = -a, b = -b; return (a < 0) ? (a+1)/b-1 : a/b; }
  67. int64_t div_ceil(int64_t a, int64_t b) { if (b < 0) a = -a, b = -b; return (a > 0) ? (a-1)/b+1 : a/b; }
  68. //mpz z_abs(mpz x) { mpz r; mpz_abs(r.get_mpz_t(), x.get_mpz_t()); return r; }
  69. //mpz z_cb(mpz x) { return x*x*x; }
  70. //mpz z_sq(mpz x) { return x*x; }
  71. //mpz z_sqrt(mpz x) { mpz r; mpz_sqrt(r.get_mpz_t(), x.get_mpz_t()); return r; }
  72. //mpz z_sqrtc(mpz x) { mpz r = z_sqrt(x); if (r*r < x) r++; return r; }
  73. //mpz z_pow(mpz x, int n) { mpz r; mpz_pow_ui(r.get_mpz_t(), x.get_mpz_t(), n); return r; }
  74. //mpz z_powmod(mpz x, mpz y, mpz m) { mpz r; mpz_powm(r.get_mpz_t(), x.get_mpz_t(), y.get_mpz_t(), m.get_mpz_t()); return r; }
  75. //mpz z_inverse(mpz x, mpz m) { mpz r; mpz_invert(r.get_mpz_t(), x.get_mpz_t(), m.get_mpz_t()); return r; }
  76. //int z_testbit(mpz z, int i) { return mpz_tstbit(z.get_mpz_t(), i); }
  77. //int f_int(mpf x) { return mpf_get_si(x.get_mpf_t()); }
  78. //mpf f_sqrt(int n) { mpf r; mpf_sqrt_ui(r.get_mpf_t(), n); return r; }
  79. //mpf f_abs(mpf x) { mpf r; mpf_abs(r.get_mpf_t(), x.get_mpf_t()); return r; }
  80. //mpf f_floor(mpf x) { mpf r; mpf_floor(r.get_mpf_t(), x.get_mpf_t()); return r; }
  81. //mpz z_div_floor(mpz a, mpz b) { mpz q; mpz_fdiv_q(q.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t()); return q; }
  82. //mpz z_div_ceil(mpz a, mpz b) { mpz q; mpz_cdiv_q(q.get_mpz_t(), a.get_mpz_t(), b.get_mpz_t()); return q; }
  83. //template<typename T> T sq(T x) { return x * x; }
  84. //double sq(double x) { return x * x; }
  85.  
  86. char to_lwr(char c) { return (c | 0x20); }
  87. char to_upr(char c) { return (c & ~0x20); }
  88. int is_lwr(char c) { return (c & 0x20); }
  89. int is_upr(char c) { return !(c & 0x20); }
  90.  
  91. // change lowercase letters to uppercase
  92. // in order for segment to become a palindrome
  93. template<typename _RanIt>
  94. void palindrome_make(_RanIt b, _RanIt e) {
  95.     e--;
  96.     while (b < e) {
  97.         if (is_lwr(*b)) *b = to_upr(*e);
  98.         if (is_lwr(*e)) *e = to_upr(*b);
  99.         b++; e--;
  100.     }
  101.     *b = to_upr(*b);
  102. }
  103.  
  104. #define SZN 500000
  105. #define SZK 300
  106.  
  107. char o[SZN+1];
  108. char u[SZK+1];
  109. int p[SZK+1];
  110. int n, m, k;
  111.  
  112. #define K 1
  113. class multi_hash {
  114.     static int M[K];
  115.     static int B[K];
  116.     static int Be[K][SZN+1];
  117.  
  118. public:
  119.     static void init() {
  120.         for (int i = 0; i < K; i++) {
  121.             Be[i][0] = 1;
  122.             for (int e = 1; e <= SZN; e++) {
  123.                 Be[i][e] = (int) ((Be[i][e - 1] * (int) B[i]));// % M[i]);
  124.             }
  125.         }
  126.     }
  127.    
  128.     int h[K];
  129.  
  130.     multi_hash(int x = 0) {
  131.         for (int i = 0; i < K; i++) {
  132.             //h[i] = x % M[i];
  133.         }
  134.     }
  135.  
  136.     multi_hash &norm() {
  137.         for (int i = 0; i < K; i++) {
  138.             //if (h[i] < 0) h[i] += M[i];
  139.         }
  140.         return *this;
  141.     }
  142.  
  143.     multi_hash roll(int e) const {
  144.         multi_hash r;
  145.         for (int i = 0; i < K; i++) {
  146.             r.h[i] = (int) ((h[i] * (int) Be[i][e]));// % M[i]);
  147.         }
  148.         return r.norm();
  149.     }
  150.  
  151.     multi_hash operator + (int x) const {
  152.         multi_hash r;
  153.         for (int i = 0; i < K; i++) {
  154.             r.h[i] = (int) ((h[i] + x));// % M[i]);
  155.         }
  156.         return r.norm();
  157.     }
  158.    
  159.     multi_hash operator - (int x) const {
  160.         multi_hash r;
  161.         for (int i = 0; i < K; i++) {
  162.             r.h[i] = (int) ((h[i] - x));// % M[i]);
  163.         }
  164.         return r.norm();
  165.     }
  166.    
  167.     multi_hash operator + (const multi_hash &other) const {
  168.         multi_hash r;
  169.         for (int i = 0; i < K; i++) {
  170.             r.h[i] = (int) ((h[i] + other.h[i]));// % M[i]);
  171.         }
  172.         return r.norm();
  173.     }
  174.    
  175.     multi_hash operator - (const multi_hash &other) const {
  176.         multi_hash r;
  177.         for (int i = 0; i < K; i++) {
  178.             r.h[i] = (int) ((h[i] - other.h[i]));// % M[i]);
  179.         }
  180.         return r.norm();
  181.     }
  182.  
  183.     bool operator == (const multi_hash &other) const {
  184.         for (int i = 0; i < K; i++) {
  185.             if (h[i] != other.h[i]) return false;
  186.         }
  187.         return true;
  188.     }
  189.  
  190.     bool operator != (const multi_hash &other) const {
  191.         return !(*this == other);
  192.     }
  193.    
  194.     bool operator < (const multi_hash &other) const {
  195.         for (int i = 0; i < K; i++) {
  196.             if (h[i] != other.h[i]) return (h[i] < other.h[i]);
  197.         }
  198.         return false;
  199.     }
  200. };
  201.  
  202. typedef multi_hash hashK;
  203. int hashK::B[K] = {        17};//,         19,         33};
  204. int hashK::M[K] = {1000000007};//, 1000000009, 1000000033};
  205. int hashK::Be[K][SZN+1];
  206.  
  207. hashK hl[SZN+1];
  208. hashK hr[SZN+1];
  209.  
  210. hashK hash_desc(int b, int e) {
  211.     return hl[e] - hl[b].roll(e - b);
  212. }
  213.  
  214. hashK hash_asc(int b, int e) {
  215.     return hr[b] - hr[e].roll(e - b);
  216. }
  217.  
  218. ll cnt = 0;
  219. int calc_palindrome_length(int mid, int odd) {
  220.     int jr = (int) (lower_bound(p, p + m, mid) - p);
  221.     int jl = jr - 1;
  222.     int e = 0;
  223.     int d = 0;
  224.     int dn = 0;
  225.     for (;;) {
  226.         cnt++;
  227.         int ql = (jl >= 0 && jl < m) ? p[jl] : -1;
  228.         int qr = (jr >= 0 && jr < m) ? p[jr] : n;
  229.         int dl = mid - ql;
  230.         int dr = qr - mid - odd + 1;
  231.         dn = min(dl, dr);
  232.         int il = mid - dn;
  233.         int ir = mid + odd + dn - 1;
  234.         if (dn > 0 && hash_desc(mid - dn + 1, mid - d) != hash_asc(mid + odd + d, mid + odd + dn - 1)) {
  235.             break;
  236.         }
  237.         if (il < 0 || ir >= n || (to_upr(o[il]) != to_upr(o[ir]) && ++e > k)) {
  238.             return 2 * (dn - 1) + odd;
  239.         }
  240.         if (dn == dl) jl--;
  241.         if (dn == dr) jr++;
  242.         d = dn;
  243.     }
  244.     int lo = d;
  245.     int hi = dn;
  246.     while (lo < hi) {
  247.         cnt++;
  248.         dn = (lo + hi) / 2;
  249.         if (hash_desc(mid - dn, mid - d) != hash_asc(mid + odd + d, mid + odd + dn)) {
  250.             hi = dn;
  251.         } else {
  252.             lo = ++dn;
  253.         }
  254.     }
  255.     return 2 * (dn - 1) + odd;
  256. }
  257.  
  258. int main() {
  259.     for (int i = 0; i < 500000; i++) o[i] = 'A';
  260.     for (int i = 500; i < 500000; i+=1700) o[i] = '?';
  261.     for (int i = 0; i < 300; i++) u[i] = 'B' + (i % 25);
  262.     k = 65;
  263.     //scanf("%s %s %d", o, u, &k);
  264.     n = (int) strlen(o);
  265.  
  266.     m = 0;
  267.     for (int i = 0; i < n; i++) {
  268.         if (o[i] == '?') {
  269.             o[i] = to_lwr(u[m]);
  270.             p[m++] = i;
  271.         }
  272.     }
  273.     p[m] = n + 1;
  274.  
  275.     hashK::init();
  276.     for (int i = 0; i < n; i++) {
  277.         hl[i+1] = hl[i].roll(1) + o[i];
  278.     }
  279.     for (int i = n-1; i >= 0; i--) {
  280.         hr[i] = hr[i+1].roll(1) + o[i];
  281.     }
  282.     printf("preproc: %d  %d ms\n", n, clock());
  283.    
  284.     int max_len = 0;
  285.     vector<int> vl(n);
  286.     for (int i = 0; i < n; i++) {
  287.         int mid = (n-1)/2 + ((i & 1) ? +(i+1)/2 : -i/2);
  288.         if (min(2*mid+1, 2*(n-1-mid)+1)+1 < max_len) continue;
  289.         int len0 = calc_palindrome_length(mid, 0);
  290.         int len1 = calc_palindrome_length(mid, 1);
  291.         int len = max(len0, len1);
  292.         vl[mid] = len;
  293.         max_len = max(len, max_len);
  294.     }
  295.     printf("%d\n", max_len);
  296.     printf("lengths: %lld  %d ms\n", cnt, clock());
  297.  
  298.     int sz = 0;
  299.     for (int mid = 0; mid < (int) vl.size(); mid++) {
  300.         if (vl[mid] == max_len) sz++;
  301.     }
  302.  
  303.     vector<pair<string, int> > w; w.reserve(sz);
  304.     for (int mid = 0; mid < (int) vl.size(); mid++) {
  305.         int len = vl[mid];
  306.         int pos = mid - len/2;
  307.         if (len == max_len) {
  308.             string s(o + pos, o + pos + len);
  309.             palindrome_make(s.begin(), s.end());
  310.             w.push_back(make_pair(s, pos + 1));
  311.         }
  312.     }
  313.     printf("palindromes: %d  %d ms\n", w.size(), clock());
  314.     sort(w.begin(), w.end());
  315.     printf("sort: %d  %d ms\n", w.size(), clock());
  316.  
  317.     for (int i = 0; i < (int) w.size(); i++) {
  318.         //printf("%s %d\n", w[i].first.c_str(), w[i].second);
  319.     }
  320.     printf("print: %d  %d ms\n", w.size(), clock());
  321.  
  322.     return 0;
  323. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement