fork(3) download
copy 
  1. /*
  2.     Problem "1157. Sub-palindromes" from acmp.ru
  3.     
  4.     (Time limit: 2 sec. Memory limit: 16 MB Difficulty: 59%)
  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^5.
  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.  
  29. #include <stdio.h>
  30. #include <cassert>
  31. #include <algorithm>
  32. #include <vector>
  33. #include <random>
  34. #include <chrono>
  35. #include <string>
  36. #include <iostream>
  37.  
  38. typedef unsigned long long ull;
  39.  
  40. // Generate random base in (before, after) open interval:
  41. int gen_base(const int before, const int after) {
  42.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  43.     std::mt19937 mt_rand(seed);
  44.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  45.     return base % 2 == 0 ? base-1 : base;
  46. }
  47.  
  48. struct PolyHash {
  49.     // -------- Static variables --------
  50.     static const int mod = (int)1e9+123; // prime mod of polynomial hashing
  51.     static std::vector<int> pow1;        // powers of base modulo mod
  52.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  53.     static int base;                     // base (point of hashing)
  54.  
  55.     // --------- Static functons --------
  56.     static inline int diff(int a, int b) { 
  57.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  58.         return (a -= b) < 0 ? a + mod : a;
  59.     }
  60.  
  61.     // -------------- Variables of class -------------
  62.     std::vector<int> pref1; // Hash on prefix modulo mod
  63.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  64.  
  65.     // Cunstructor from string:
  66.     PolyHash(const std::string& s)
  67.         : pref1(s.size()+1u, 0)
  68.         , pref2(s.size()+1u, 0)
  69.     {
  70.         assert(base < mod);
  71.         const int n = s.size(); // Firstly calculated needed power of base:
  72.         while ((int)pow1.size() <= n) {
  73.             pow1.push_back(1LL * pow1.back() * base % mod);
  74.             pow2.push_back(pow2.back() * base);
  75.         }
  76.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  77.             assert(base > s[i]);
  78.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  79.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  80.         }
  81.     }
  82.  
  83.     // Polynomial hash of subsequence [pos, pos+len)
  84.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  85.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  86.         int hash1 = pref1[pos+len] - pref1[pos];
  87.         ull hash2 = pref2[pos+len] - pref2[pos];
  88.         if (hash1 < 0) hash1 += mod;
  89.         if (mxPow != 0) {
  90.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  91.             hash2 *= pow2[mxPow-(pos+len-1)];
  92.         }
  93.         return std::make_pair(hash1, hash2);
  94.     }
  95. };
  96.  
  97. // Init static variables of PolyHash class:
  98. int PolyHash::base((int)1e9+7);    
  99. std::vector<int> PolyHash::pow1{1};
  100. std::vector<ull> PolyHash::pow2{1};
  101.  
  102. int main() {
  103.     static char buf[1+100000];
  104.     scanf("%1000000s", buf);
  105.     std::string a(buf);
  106.     std::string b(a);
  107.     std::reverse(b.begin(), b.end());
  108.  
  109.     // Gen random base of hashing:
  110.     PolyHash::base = gen_base(256, PolyHash::mod);
  111.  
  112.     // Cunstruct polynomial hashes on prefix of original and reversed string:
  113.     PolyHash hash_a(a), hash_b(b);
  114.  
  115.     // Get length of strings (mxPow == n)
  116.     const int n = (int)a.size();
  117.  
  118.     ull answ = 0;
  119.     for (int i = 0, j = n-1; i < n; ++i, --j) {
  120.         // Palindromes odd length:
  121.         int low = 0, high = std::min(n-i, n-j)+1;
  122.         while (high - low > 1) {
  123.             int mid = (low + high) / 2;
  124.             if (hash_a(i, mid, n) == hash_b(j, mid, n)) {
  125.                 low = mid;
  126.             } else {
  127.                 high = mid;
  128.             }
  129.         }
  130.         answ += low;
  131.         // Palindromes even length:
  132.         low = 0, high = std::min(n-i-1, n-j)+1;
  133.         while (high - low > 1) {
  134.             int mid = (low + high) / 2;
  135.             if (hash_a(i+1, mid, n) == hash_b(j, mid, n)) {
  136.                 low = mid;
  137.             } else {
  138.                 high = mid;
  139.             }
  140.         }
  141.         answ += low;
  142.     }
  143.     std::cout << answ;
  144.     return 0;
  145. }
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
ABACABADABACABA
stdout
copy 
32
https://ideone.com/6BWI94
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!