Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_DEPRECATE
- #define _SCL_SECURE_NO_WARNINGS
- //#define _CRT_RAND_S
- //#include <windows.h>
- //#include <tchar.h>
- //#include <atlbase.h>
- //#include <winerror.h>
- //#define BOOST_FILESYSTEM_NO_DEPRECATED
- //#include <boost/filesystem.hpp>
- //#include <boost/filesystem/fstream.hpp>
- //#include <boost/regex.hpp>
- //#include <boost/algorithm/string.hpp>
- #include <stdint.h>
- #include <climits>
- #include <ctime>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <map>
- #include <set>
- #include <list>
- #include <queue>
- #include <deque>
- #include <string>
- #include <bitset>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- //#include <unordered_set>
- //#include <unordered_map>
- using namespace std;
- //using namespace tr1;
- typedef unsigned int uint;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int, int> pii;
- typedef pair<ll, int> pli;
- typedef pair<ll, ll> pll;
- //#include <gmpxx.h>
- //typedef mpz_class mpz;
- //typedef mpq_class mpq;
- //typedef mpf_class mpf;
- //typedef pair<mpz, mpz> pzz;
- //mpz int64_to_mpz(int64_t x) { return (mpz(int32_t(x >> 32)) << 32) | mpz(uint32_t(x & 0xFFFFFFFF)); }
- //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()); }
- //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)); }
- //int is_prime(int64_t x, int iter = 8) { return mpz_probab_prime_p(int64_to_mpz(x).get_mpz_t(), iter); }
- //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); }
- //int64_t cb(int32_t x) { return int64_t(x)*x*x; }
- //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; }
- int64_t isq(int32_t x) { return int64_t(x)*x; }
- int64_t isq(int64_t x) { return int64_t(x)*x; }
- 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; }
- //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; }
- //int is_square(int64_t x) { return (isq(isqrt(x)) == x); }
- 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; }
- 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; }
- //mpz z_abs(mpz x) { mpz r; mpz_abs(r.get_mpz_t(), x.get_mpz_t()); return r; }
- //mpz z_cb(mpz x) { return x*x*x; }
- //mpz z_sq(mpz x) { return x*x; }
- //mpz z_sqrt(mpz x) { mpz r; mpz_sqrt(r.get_mpz_t(), x.get_mpz_t()); return r; }
- //mpz z_sqrtc(mpz x) { mpz r = z_sqrt(x); if (r*r < x) r++; return r; }
- //mpz z_pow(mpz x, int n) { mpz r; mpz_pow_ui(r.get_mpz_t(), x.get_mpz_t(), n); return r; }
- //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; }
- //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; }
- //int z_testbit(mpz z, int i) { return mpz_tstbit(z.get_mpz_t(), i); }
- //int f_int(mpf x) { return mpf_get_si(x.get_mpf_t()); }
- //mpf f_sqrt(int n) { mpf r; mpf_sqrt_ui(r.get_mpf_t(), n); return r; }
- //mpf f_abs(mpf x) { mpf r; mpf_abs(r.get_mpf_t(), x.get_mpf_t()); return r; }
- //mpf f_floor(mpf x) { mpf r; mpf_floor(r.get_mpf_t(), x.get_mpf_t()); return r; }
- //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; }
- //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; }
- //template<typename T> T sq(T x) { return x * x; }
- //double sq(double x) { return x * x; }
- char to_lwr(char c) { return (c | 0x20); }
- char to_upr(char c) { return (c & ~0x20); }
- int is_lwr(char c) { return (c & 0x20); }
- int is_upr(char c) { return !(c & 0x20); }
- // change lowercase letters to uppercase
- // in order for segment to become a palindrome
- template<typename _RanIt>
- void palindrome_make(_RanIt b, _RanIt e) {
- e--;
- while (b < e) {
- if (is_lwr(*b)) *b = to_upr(*e);
- if (is_lwr(*e)) *e = to_upr(*b);
- b++; e--;
- }
- *b = to_upr(*b);
- }
- #define SZN 500000
- #define SZK 300
- char o[SZN+1];
- char u[SZK+1];
- int p[SZK+1];
- int n, m, k;
- #define K 1
- class multi_hash {
- static int M[K];
- static int B[K];
- static int Be[K][SZN+1];
- public:
- static void init() {
- for (int i = 0; i < K; i++) {
- Be[i][0] = 1;
- for (int e = 1; e <= SZN; e++) {
- Be[i][e] = (int) ((Be[i][e - 1] * (int) B[i]));// % M[i]);
- }
- }
- }
- int h[K];
- multi_hash(int x = 0) {
- for (int i = 0; i < K; i++) {
- //h[i] = x % M[i];
- }
- }
- multi_hash &norm() {
- for (int i = 0; i < K; i++) {
- //if (h[i] < 0) h[i] += M[i];
- }
- return *this;
- }
- multi_hash roll(int e) const {
- multi_hash r;
- for (int i = 0; i < K; i++) {
- r.h[i] = (int) ((h[i] * (int) Be[i][e]));// % M[i]);
- }
- return r.norm();
- }
- multi_hash operator + (int x) const {
- multi_hash r;
- for (int i = 0; i < K; i++) {
- r.h[i] = (int) ((h[i] + x));// % M[i]);
- }
- return r.norm();
- }
- multi_hash operator - (int x) const {
- multi_hash r;
- for (int i = 0; i < K; i++) {
- r.h[i] = (int) ((h[i] - x));// % M[i]);
- }
- return r.norm();
- }
- multi_hash operator + (const multi_hash &other) const {
- multi_hash r;
- for (int i = 0; i < K; i++) {
- r.h[i] = (int) ((h[i] + other.h[i]));// % M[i]);
- }
- return r.norm();
- }
- multi_hash operator - (const multi_hash &other) const {
- multi_hash r;
- for (int i = 0; i < K; i++) {
- r.h[i] = (int) ((h[i] - other.h[i]));// % M[i]);
- }
- return r.norm();
- }
- bool operator == (const multi_hash &other) const {
- for (int i = 0; i < K; i++) {
- if (h[i] != other.h[i]) return false;
- }
- return true;
- }
- bool operator != (const multi_hash &other) const {
- return !(*this == other);
- }
- bool operator < (const multi_hash &other) const {
- for (int i = 0; i < K; i++) {
- if (h[i] != other.h[i]) return (h[i] < other.h[i]);
- }
- return false;
- }
- };
- typedef multi_hash hashK;
- int hashK::B[K] = { 17};//, 19, 33};
- int hashK::M[K] = {1000000007};//, 1000000009, 1000000033};
- int hashK::Be[K][SZN+1];
- hashK hl[SZN+1];
- hashK hr[SZN+1];
- hashK hash_desc(int b, int e) {
- return hl[e] - hl[b].roll(e - b);
- }
- hashK hash_asc(int b, int e) {
- return hr[b] - hr[e].roll(e - b);
- }
- ll cnt = 0;
- int calc_palindrome_length(int mid, int odd) {
- int jr = (int) (lower_bound(p, p + m, mid) - p);
- int jl = jr - 1;
- int e = 0;
- int d = 0;
- int dn = 0;
- for (;;) {
- cnt++;
- int ql = (jl >= 0 && jl < m) ? p[jl] : -1;
- int qr = (jr >= 0 && jr < m) ? p[jr] : n;
- int dl = mid - ql;
- int dr = qr - mid - odd + 1;
- dn = min(dl, dr);
- int il = mid - dn;
- int ir = mid + odd + dn - 1;
- if (dn > 0 && hash_desc(mid - dn + 1, mid - d) != hash_asc(mid + odd + d, mid + odd + dn - 1)) {
- break;
- }
- if (il < 0 || ir >= n || (to_upr(o[il]) != to_upr(o[ir]) && ++e > k)) {
- return 2 * (dn - 1) + odd;
- }
- if (dn == dl) jl--;
- if (dn == dr) jr++;
- d = dn;
- }
- int lo = d;
- int hi = dn;
- while (lo < hi) {
- cnt++;
- dn = (lo + hi) / 2;
- if (hash_desc(mid - dn, mid - d) != hash_asc(mid + odd + d, mid + odd + dn)) {
- hi = dn;
- } else {
- lo = ++dn;
- }
- }
- return 2 * (dn - 1) + odd;
- }
- int main() {
- for (int i = 0; i < 500000; i++) o[i] = 'A';
- for (int i = 500; i < 500000; i+=1700) o[i] = '?';
- for (int i = 0; i < 300; i++) u[i] = 'B' + (i % 25);
- k = 65;
- //scanf("%s %s %d", o, u, &k);
- n = (int) strlen(o);
- m = 0;
- for (int i = 0; i < n; i++) {
- if (o[i] == '?') {
- o[i] = to_lwr(u[m]);
- p[m++] = i;
- }
- }
- p[m] = n + 1;
- hashK::init();
- for (int i = 0; i < n; i++) {
- hl[i+1] = hl[i].roll(1) + o[i];
- }
- for (int i = n-1; i >= 0; i--) {
- hr[i] = hr[i+1].roll(1) + o[i];
- }
- printf("preproc: %d %d ms\n", n, clock());
- int max_len = 0;
- vector<int> vl(n);
- for (int i = 0; i < n; i++) {
- int mid = (n-1)/2 + ((i & 1) ? +(i+1)/2 : -i/2);
- if (min(2*mid+1, 2*(n-1-mid)+1)+1 < max_len) continue;
- int len0 = calc_palindrome_length(mid, 0);
- int len1 = calc_palindrome_length(mid, 1);
- int len = max(len0, len1);
- vl[mid] = len;
- max_len = max(len, max_len);
- }
- printf("%d\n", max_len);
- printf("lengths: %lld %d ms\n", cnt, clock());
- int sz = 0;
- for (int mid = 0; mid < (int) vl.size(); mid++) {
- if (vl[mid] == max_len) sz++;
- }
- vector<pair<string, int> > w; w.reserve(sz);
- for (int mid = 0; mid < (int) vl.size(); mid++) {
- int len = vl[mid];
- int pos = mid - len/2;
- if (len == max_len) {
- string s(o + pos, o + pos + len);
- palindrome_make(s.begin(), s.end());
- w.push_back(make_pair(s, pos + 1));
- }
- }
- printf("palindromes: %d %d ms\n", w.size(), clock());
- sort(w.begin(), w.end());
- printf("sort: %d %d ms\n", w.size(), clock());
- for (int i = 0; i < (int) w.size(); i++) {
- //printf("%s %d\n", w[i].first.c_str(), w[i].second);
- }
- printf("print: %d %d ms\n", w.size(), clock());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement