fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. long long n, sizeS;
  5. string s;
  6. map<long long, long long> dem_l, dem_r, ans_r, ans_l;
  7. #define base 31
  8. long long MOD = 1e9 + 7;
  9. long long hash_l[1000005];
  10. long long poww[1000005];
  11. long long hash_r[1000005];
  12. long long gethash_l(long long l, long long r)
  13. {
  14.     return (hash_l[r] - hash_l[l - 1] * poww[r - l + 1] + MOD * MOD) % MOD;
  15. }
  16. long long gethash_r(long long l, long long r)
  17. {
  18.     return (hash_r[l] - hash_r[r + 1] * poww[r - l + 1] + MOD * MOD) % MOD;
  19. }
  20. int main()
  21. {
  22.     ios_base::sync_with_stdio(false);
  23.     cin.tie(NULL);
  24.     cout.tie(NULL);
  25.     cin >> n;
  26.     poww[0] = 1;
  27.     for (int i = 1; i <= 1e6; i ++) poww[i] = (poww[i - 1] % MOD * base % MOD) % MOD;
  28.     while (n --)
  29.     {
  30.         cin >> sizeS >> s;
  31.         s = ' ' + s;
  32.         hash_l[0] = 0;
  33.         hash_r[sizeS + 1] = 0;
  34.         for (int i = 1; i <= sizeS; i ++) hash_l[i] = (hash_l[i - 1] * base + s[i] - 'a' + 1) % MOD;
  35.         dem_l[hash_l[sizeS]] ++;
  36.         for (int i = sizeS; i >= 1; i --) hash_r[i] = (hash_r[i + 1] * base + s[i] - 'a' + 1) % MOD;
  37.         dem_r[hash_r[1]] ++;
  38.  
  39.  
  40.         for (int i = 1; i <= sizeS; i ++)
  41.         {
  42.             /// i thằng đầu tiên
  43.             /// phần còn lại của xâu sẽ là [i, size] co la xdx hay khong 
  44.  
  45.  
  46.             long long size = (sizeS - i + 1) / 2;
  47.             if (gethash_l(i, i + size - 1) == hash_r[sizeS - size + 1]) ans_l[hash_l[i - 1]] ++;
  48.         }
  49.  
  50.         for (int i = sizeS; i >= 1; i --)
  51.         {
  52.             long long size = i / 2;
  53.             if (gethash_r(i - size + 1, i) == hash_l[size]) ans_r[hash_r[i + 1]] ++;
  54.         }
  55.     }
  56.     long long ans = 0;
  57.     for(auto x : dem_l)
  58.     {
  59.         ans += x.second * dem_r[x.first];
  60.         ans += x.second * ans_r[x.first];
  61.     }
  62.     for(auto x : dem_r) ans += x.second * ans_l[x.first];
  63.     cout << ans;
  64. }
  65.  
Success #stdin #stdout 0.03s 13748KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AQ9Q7U
language:
C++14 (gcc 8.3)
created:
30 days 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!