fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define TIME (1.0* clock()/CLOCKS_PER_SEC)
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define id1 (id<<1)
  6. #define id2 (id<<1)|1
  7. #define ll long long
  8. #define ii pair<int,int>
  9. #define vi vector<int>
  10. #define vii vector<pair<int,int>> 
  11. #define vl vector<long long>
  12. #define vll vector <pair<ll,ll>>
  13. #define li pair<long long,int>
  14. #define vil vector <pair<int,ll>>
  15. #define db double
  16. #define ff first
  17. #define ss second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define FOR(i, a, b) for (int i = (a); i <=(b); i++)
  21. #define F0R(i, a) FOR(i, 0, a-1)
  22. #define ROF(i, a, b) for (int i = (b); i >= (a); i--)
  23. #define R0F(i, a) ROF(i, 0, a-1)
  24. #define rep(a) F0R(_, a)
  25. #define each(a, x) for (auto &a : x)
  26. #define ALL(x) (x).begin(),(x).end()
  27. #define pq priority_queue <li, vector <li>, greater <li>> 
  28. using namespace std;
  29. const int maxn=1e5+5;
  30. //const int MOD=1e9+7;
  31. //const int MOD=998244353;
  32. //const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
  33. int m;
  34.  
  35. vector<array<int,26>> T1; 
  36. vector<array<int,26>> T2; 
  37. const int BASE = 29;
  38. const int MOD = 1e9 + 7;
  39. int isEnd1[maxn]; 
  40. int isEnd2[maxn]; 
  41. string S[maxn];   
  42. string R[maxn];
  43. int cnt[maxn];
  44. vector<ll> powB;
  45. void precompute_pow(int max_len){
  46.     powB.resize(max_len + 1);
  47.     powB[0] = 1;
  48.     for (int i = 1; i <= max_len; i++) {
  49.         powB[i] = (powB[i-1] * BASE) % MOD;
  50.     }
  51. }
  52.  
  53. void addT1(string s){
  54.     int root = 0;
  55.     for (char x : s) {
  56.         int k = x - 'a';
  57.         if (T1[root][k] == 0) {
  58.             T1.emplace_back();
  59.             T1[root][k] = T1.size()-1;
  60.         }
  61.         root = T1[root][k];
  62.     }
  63.     isEnd1[root]++;
  64. }
  65.  
  66. void addT2(string s){
  67.     int root = 0;
  68.     for (char x : s) {
  69.         int k = x - 'a';
  70.         if (T2[root][k] == 0) {
  71.             T2.emplace_back();
  72.             T2[root][k] = T2.size()-1;
  73.         }
  74.         root = T2[root][k];
  75.     }
  76.     isEnd2[root]++;
  77. }
  78.  
  79. void build(const string &s) {
  80.     int n = s.length();
  81.     if (powB.empty()) precompute_pow(n);
  82.  
  83.     vector<ll> hashF(n + 1), hashR(n + 1);
  84.  
  85.     hashF[0] = 0;
  86.     for (int i=1;i<=n;i++){
  87.         hashF[i]=(hashF[i-1]*BASE+s[i-1])%MOD;
  88.     }
  89.  
  90.  
  91.     hashR[n] = 0;
  92.     for (int i=n-1;i>=0;i--){
  93.         hashR[i] = (hashR[i+1] * BASE + s[i]) % MOD;
  94.     }
  95.  
  96.     auto checkpalindrome = [&](int l, int r) {
  97.         ll forward = (hashF[r+1] - hashF[l] * powB[r-l+1] % MOD + MOD) % MOD;
  98.         ll reverse = (hashR[l] - hashR[r+1] * powB[r-l+1] % MOD + MOD) % MOD;
  99.         return forward == reverse;
  100.     };
  101.  
  102.  
  103.     int root = 0;
  104.     for (int i=0;i<n;i++){
  105.         int k = s[i] - 'a';
  106.         if (T1[root][k] == 0) break;
  107.         root = T1[root][k];
  108.         if (checkpalindrome(i+1, n-1)) {
  109.             cnt[root]++;
  110.         }
  111.     }
  112.  
  113. }
  114.  
  115. int countPalindrome(string s){
  116.   int n = s.length();
  117.   int res=0;
  118.     if (powB.empty()) precompute_pow(n);
  119.  
  120.     vector<ll> hashF(n + 1), hashR(n + 1);
  121.  
  122.     hashF[0] = 0;
  123.     for (int i=1;i<=n;i++){
  124.         hashF[i]=(hashF[i-1]*BASE+s[i-1])%MOD;
  125.     }
  126.  
  127.  
  128.     hashR[n] = 0;
  129.     for (int i=n-1;i>=0;i--){
  130.         hashR[i] = (hashR[i+1] * BASE + s[i]) % MOD;
  131.     }
  132.  
  133.     auto checkpalindrome = [&](int l, int r) {
  134.         ll forward = (hashF[r+1] - hashF[l] * powB[r-l+1] % MOD + MOD) % MOD;
  135.         ll reverse = (hashR[l] - hashR[r+1] * powB[r-l+1] % MOD + MOD) % MOD;
  136.         return forward == reverse;
  137.     };
  138.  
  139.     int root1=0;
  140.     int root2=0;
  141.     for(int i=0;i<n;i++){
  142.        int k = s[i] - 'a';
  143.        if(T2[root2][k]==0) break;
  144.        root1=T1[root1][k];
  145.        root2=T2[root2][k];
  146.        if(isEnd1[root2] and checkpalindrome(i+1, n-1)) res+=isEnd2[root2]; // Si>Sj;
  147.  
  148.  
  149.     }
  150.     res+=isEnd2[root2]; //Si==Sj;
  151.     res+=cnt[root2];//Si<Sj;
  152.     return res;
  153. }
  154.  
  155. void solve(){
  156.  
  157.     T1.emplace_back();
  158.     T2.emplace_back();
  159.  
  160.     cin >> m;
  161.     for(int i = 1; i <= m; i++){
  162.         cin >> S[i];
  163.  
  164.         addT1(S[i]);
  165.  
  166.         R[i]= S[i];
  167.         reverse(R[i].begin(), R[i].end());
  168.         addT2(R[i]);
  169.     }
  170.  
  171.     for(int i=1;i<=m;i++) build(R[i]);
  172.     int val=0;
  173.     for(int i=1;val<=m;val++) val+=countPalindrome(S[i]);
  174.  
  175.     cout<<val;
  176.     return;    
  177. }
  178.  
  179. signed main(){
  180.     ios_base::sync_with_stdio(false);
  181.     cin.tie(NULL);cout.tie(NULL);
  182.     if (fopen("TASK.INP", "r")){
  183.         freopen("TASK.INP", "r", stdin);
  184.         freopen("TASK.OUT", "w", stdout);
  185.     }
  186.     int ntest = 1;
  187.     //cin >> ntest;
  188.  
  189.     for(int i = 1; i <= ntest; i++) solve();
  190.     cerr << "\n" << "Time elapsed " << TIME << "s.\n";
  191.     return 0;
  192. }
Success #stdin #stdout #stderr 0.01s 9972KB
comments (?)
stdin
copy 
3
a
b
ab
stdout
copy 
4
stderr
copy 
Time elapsed 0.00717s.
https://ideone.com/0ZhJq8
language:
C++14 (gcc 8.3)
created:
13 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!