fork download
copy 
  1. /*
  2.     Problem "1159. Sub-palindromes" from acmp.ru
  3.     
  4.     (Time limit: 2 sec. Memory limit: 32 MB Difficulty: 79%)
  5.  
  6.     A string is called a palindrome, if it is read equally from left to right, 
  7.     and from right to left. For example, the lines "abba" and "ata" are 
  8.     palindromes.
  9.  
  10.     A substring of some string is a nonempty sequence of consecutive characters 
  11.     in the original string.
  12.  
  13.     Write a program that calculates how many substrings of this string are 
  14.     palindromes.
  15.  
  16.     INPUT:
  17.  
  18.     In a single line of the INPUT.TXT input file, a string consisting of 
  19.     characters with ASCII codes from 33 to 127. A string length does 
  20.     not exceed 10^6.
  21.  
  22.     OUTPUT:
  23.  
  24.     Write the answer in the output file OUTPUT.TXT.
  25.     
  26.     Solution: polynomial hash, binary search, O(n log(n))
  27.     
  28.     EXTREMELY SPEED, 31 MB Memory
  29. */
  30.  
  31. #include <stdio.h>
  32. #include <cassert>
  33. #include <algorithm>
  34. #include <vector>
  35. #include <random>
  36. #include <chrono>
  37. #include <string>
  38. #include <iostream>
  39.  
  40. typedef unsigned long long ull;
  41.  
  42. // Generate random base in (before, after) open interval:
  43. int gen_base(const int before, const int after) {
  44.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  45.     seed ^= ull(new ull);
  46.     std::mt19937 mt_rand(seed);
  47.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  48.     return base % 2 == 0 ? base-1 : base;
  49. }
  50.  
  51. struct PolyHash {
  52.     // -------- Static variables --------
  53.     static std::vector<int> pow1;        // powers of base modulo mod
  54.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  55.     static int base;                     // base (point of hashing)
  56.  
  57.     // --------- Static functons --------
  58.     static inline int diff(int a, int b) { 
  59.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  60.         return (a -= b) < 0 ? a + 2147483647 : a;
  61.     }
  62.  
  63.     static inline int mod(ull x) {
  64.         x += 2147483647;
  65.         x = (x >> 31) + (x & 2147483647);
  66.         return int((x >> 31) + (x & 2147483647));
  67.     }
  68.  
  69.     // -------------- Variables of class -------------
  70.     std::vector<int> pref1; // Hash on prefix modulo mod
  71.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  72.  
  73.     // Get power of base by modulo mod:
  74.     inline int get_pow1(int p) const {
  75.         static int __base[4] = {1, base, mod(ull(base) * base), mod(mod(ull(base) * base) * ull(base))};
  76.         return mod(ull(__base[p % 4]) * pow1[p / 4]);
  77.     }
  78.  
  79.     // Get power of base by modulo 2^64:
  80.     inline ull get_pow2(int p) const {
  81.         static ull __base[4] = {ull(1), ull(base), ull(base) * base, ull(base) * base * base};
  82.         return pow2[p / 4] * __base[p % 4];
  83.     }
  84.  
  85.     // Cunstructor from string:
  86.     PolyHash(const std::string& s)
  87.         : pref1(s.size()+1u, 0)
  88.         , pref2(s.size()+1u, 0)
  89.     {
  90.         const int n = s.size(); 
  91.         pow1.reserve((n+3)/4);
  92.         pow2.reserve((n+3)/4);
  93.         // Firstly calculated needed power of base:
  94.         int pow1_4 = mod(ull(base) * base); // base^2 mod 2^31-1
  95.         pow1_4 = mod(ull(pow1_4) * pow1_4); // base^4 mod 2^31-1
  96.         ull pow2_4 = ull(base) * base;      // base^2 mod 2^64
  97.         pow2_4 *= pow2_4;                   // base^4 mod 2^64
  98.         while (4 * (int)pow1.size() <= n) {
  99.             pow1.push_back(mod((ull)pow1.back() * pow1_4));
  100.             pow2.push_back(pow2.back() * pow2_4);
  101.         }
  102.         int curr_pow1 = 1;
  103.         ull curr_pow2 = 1;
  104.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  105.             assert(base > s[i]);
  106.             pref1[i+1] = mod(pref1[i] + (ull)s[i] * curr_pow1);
  107.             pref2[i+1] = pref2[i] + s[i] * curr_pow2;
  108.             curr_pow1 = mod((ull)curr_pow1 * base);
  109.             curr_pow2 *= base;
  110.         }
  111.     }
  112.  
  113.     // Polynomial hash of subsequence [pos, pos+len)
  114.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  115.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  116.         int hash1 = pref1[pos+len] - pref1[pos];
  117.         ull hash2 = pref2[pos+len] - pref2[pos];
  118.         if (hash1 < 0) hash1 += 2147483647;
  119.         if (mxPow != 0) {
  120.             hash1 = mod((ull)hash1 * get_pow1(mxPow-(pos+len-1)));
  121.             hash2 *= get_pow2(mxPow-(pos+len-1));
  122.         }
  123.         return std::make_pair(hash1, hash2);
  124.     }
  125. };
  126.  
  127. // Init static variables of PolyHash class:
  128. int PolyHash::base((int)1e9+7);    
  129. std::vector<int> PolyHash::pow1{1};
  130. std::vector<ull> PolyHash::pow2{1};
  131.  
  132. int main() {
  133.     std::string a;
  134.     {
  135.         std::vector<char> buf(1+1000000);
  136.         scanf("%1000000s", &buf[0]);
  137.         a = std::string(&buf[0]);
  138.     }
  139.  
  140.     // Gen random base of hashing:
  141.     PolyHash::base = gen_base(256, 2147483647);
  142.  
  143.     // Cunstruct polynomial hashes on prefix of original and reversed string:
  144.     PolyHash hash_a(a); 
  145.     std::reverse(a.begin(), a.end());
  146.     PolyHash hash_b(a);
  147.  
  148.     // Get length of strings (mxPow == n)
  149.     const int n = (int)a.size();
  150.  
  151.     ull answ = 0;
  152.     for (int i = 0, j = n-1; i < n; ++i, --j) {
  153.         // Palindromes odd length:
  154.         int low = 0, high = std::min(n-i, n-j)+1;
  155.         while (high - low > 1) {
  156.             int mid = (low + high) / 2;
  157.             if (hash_a(i, mid, n) == hash_b(j, mid, n)) {
  158.                 low = mid;
  159.             } else {
  160.                 high = mid;
  161.             }
  162.         }
  163.         answ += low;
  164.         // Palindromes even length:
  165.         low = 0, high = std::min(n-i-1, n-j)+1;
  166.         while (high - low > 1) {
  167.             int mid = (low + high) / 2;
  168.             if (hash_a(i+1, mid, n) == hash_b(j, mid, n)) {
  169.                 low = mid;
  170.             } else {
  171.                 high = mid;
  172.             }
  173.         }
  174.         answ += low;
  175.     }
  176.     std::cout << answ;
  177.     return 0;
  178. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
ABACABADABACABA
stdout
copy 
32
https://ideone.com/z3PJQH
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!