fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define mset(x,val) memset(x,val,sizeof(x))
  6. #define allof(x) x.begin(), x.end()
  7. #define fi first
  8. #define se second
  9.  
  10. using ll = long long;
  11. using vi = vector<int>;
  12. using vii = vector<vector<int>>;
  13. using vl = vector<long long>;
  14. using vll = vector<vector<long long>>;
  15. using vb = vector<bool>;
  16. using vbb = vector<vector<bool>>;
  17. using mii = map<int,int>;
  18. using umii = unordered_map<int,int>;
  19. using pii = pair<int,int>;
  20. using pll = pair<long long,long long>;
  21. using pli = pair<long long, int>;
  22. using pil = pair<int, long long>;
  23. #define __builtin_popcount __builtin_popcountll
  24. #define BIT(x, i) (((x) >> (i)) & 1)
  25. #define MASK(x) ((1ll << (x)))
  26. #define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n'; 
  27.  
  28. const int MOD = 1e9 + 7;
  29. const int maxn = 1e5 + 5;
  30.  
  31. int a, b, m, n, k, q;
  32.  
  33. struct Eertree
  34. {
  35.     struct Node
  36.     {
  37.         int len;
  38.         int link;
  39.         int next[26];
  40.         int cnt;
  41.         int s_cnt;
  42.         int first_pos;
  43.  
  44.         Node (int _n)
  45.         {
  46.             len = _n;
  47.             link = 0;
  48.             cnt = 0;
  49.             s_cnt = 0;
  50.             mset(next, 0);
  51.         }
  52.     };
  53.  
  54.     int n;
  55.     vector <Node> tree;
  56.     string s;
  57.     int last;
  58.  
  59.     Eertree(int _n)
  60.     {
  61.         n = _n;
  62.         tree.reserve(n+3);
  63.         tree.push_back(Node(-1));
  64.         tree.push_back(Node(0));
  65.  
  66.         tree[0].link = 0;
  67.         tree[1].link = 0;
  68.  
  69.         last = 1;
  70.         s="";
  71.     }
  72.  
  73.     int get_link(int v, int pos)
  74.     {
  75.         while (1)
  76.         {
  77.             int curlen = tree[v].len;
  78.             if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
  79.             v = tree[v].link;
  80.         }
  81.         return v;    
  82.     }
  83.  
  84.     void add_char(char c)
  85.     {
  86.         int pos = s.size();
  87.         s+=c;
  88.         int cur = get_link(last, pos);
  89.  
  90.         int cidx = c-'a';
  91.  
  92.         if (tree[cur].next[cidx])
  93.         {
  94.             last = tree[cur].next[cidx];
  95.             tree[last].cnt++;
  96.             tree[last].s_cnt++;
  97.             return;
  98.         }
  99.  
  100.         int new_node = tree.size();
  101.         tree.push_back(Node(tree[cur].len + 2));
  102.         tree[new_node].first_pos = pos;
  103.  
  104.         tree[cur].next[cidx] = new_node;
  105.  
  106.         if (tree[new_node].len == 1) tree[new_node].link = 1;
  107.         else
  108.         {
  109.             int num = get_link(tree[cur].link, pos);
  110.             tree[new_node].link = tree[num].next[cidx];
  111.         }
  112.  
  113.         tree[new_node].cnt = 1;
  114.         tree[new_node].s_cnt = 1;
  115.         last = new_node;
  116.     }
  117.  
  118.     void build(string str)
  119.     {
  120.         for (char c : str) add_char(c);
  121.     }
  122.  
  123.     void propagate()
  124.     {
  125.         for (int i=tree.size()-1; i>=2; --i)
  126.         {
  127.             tree[tree[i].link].s_cnt += tree[i].s_cnt;
  128.         }
  129.     }
  130.  
  131.     int distinct_palin_cnt()
  132.     {
  133.         return tree.size() - 2; 
  134.     }
  135.  
  136.     int palin_cnt()
  137.     {
  138.         int res=0;
  139.  
  140.         for (int i=2; i<tree.size(); ++i) res+=tree[i].s_cnt;
  141.  
  142.         return res;
  143.     }
  144.  
  145.  
  146. };
  147.  
  148. string s;
  149.  
  150. void Input()
  151. {
  152.     cin>>s;
  153.     Eertree Eet = Eertree(s.size());
  154.     Eet.build(s);
  155.     Eet.propagate();
  156.     cout<<Eet.palin_cnt();
  157.  
  158. }
  159.  
  160. int main()
  161. {
  162.  
  163.     ios::sync_with_stdio(0);
  164.     cin.tie(0);
  165.     cout.tie(0);
  166.  
  167.     Input();
  168.     return 0;
  169. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
malayalam
stdout
copy 
15
https://ideone.com/OhZEHV
problem NUMOFPAL, based on SPOJ submission 35574116 (CPP14), 2026-03-04 06:25:26
Eertree template (counting palindromic substrings, distinct palindromic substrings, track palindromic subtrings)
O(n) build
O(n) propagate
O(1) count distinct
O(n) count total
language:
C++14 (gcc 8.3)
created:
2 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!