fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #include <stdlib.h>
  7. #include <string>
  8. #include <bitset>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <queue>
  13. #include <algorithm>
  14. #include <sstream>
  15. #include <stack>
  16. #include <iomanip>
  17. using namespace std;
  18. #define pb push_back
  19. #define mp make_pair
  20. typedef pair<int,int> pii;
  21. typedef long long ll;
  22. typedef double ld;
  23. typedef vector<int> vi;
  24. #define fi first
  25. #define se second
  26. #define fe first
  27. #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
  28. #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
  29. #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
  30. #define es(x,e) (int e=fst[x];e;e=nxt[e])
  31. #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
  32. #define SZ 66666
  33. int n;
  34. const int MOD=1000000007;
  35. ll cm[SZ],cmn[SZ];
  36. ll qp(ll a,ll b)
  37. {
  38.     ll ans=1;
  39.     while(b)
  40.     {
  41.         if(b&1) ans=ans*a%MOD;
  42.         a=a*a%MOD; b>>=1;
  43.     }
  44.     return ans;
  45. }
  46. struct HashKMP
  47. {
  48. char s[SZ+1]; int n;
  49. ll hash[SZ+1];
  50. void pre()
  51. {
  52.     n=strlen(s);
  53.     for(int i=n-1;i>=0;i--) hash[i]=(hash[i+1]+cm[n-1-i]*(s[i]-'a'+1)%MOD)%MOD;
  54. }
  55. inline ll ghash(int l,int r)
  56. {
  57.     return ((hash[l]-hash[r+1])*cmn[n-1-r]%MOD+MOD)%MOD;
  58. }
  59. }a,b;
  60. inline ll hsh(int l,int r)
  61. {return a.ghash(n-r,n-l);}
  62. inline ll hshf(int l,int r)
  63. {return b.ghash(l-1,r-1);}
  64. char s[SZ];
  65. int wo[1005][1005];
  66. int main()
  67. {
  68.     cm[0]=cmn[0]=1; ll gg=qp(129,MOD-2);
  69.     for(int i=1;i<SZ;i++) cm[i]=cm[i-1]*129%MOD;
  70.     for(int i=1;i<SZ;i++) cmn[i]=cmn[i-1]*gg%MOD;
  71. 	scanf("%s",s+1); n=strlen(s+1);
  72. 	reverse(s+1,s+1+n);
  73. 	strcpy(a.s,s+1);
  74. 	reverse(s+1,s+1+n);
  75. 	strcpy(b.s,s+1);
  76. 	a.pre(); b.pre();
  77. 	ll ans=0;
  78. 	for(int i=1;i<=n;++i)
  79. 		for(int j=1;i+j<=n;++j)
  80. 		{
  81. 			if(s[i]!=s[i+j]) wo[i][i+j]=0;
  82. 			else wo[i][i+j]=wo[i-1][i+j+1]+1;
  83. 			ans+=wo[i][i+j];
  84. 		}
  85. 	for(int i=1;i<=n;++i)
  86. 	{
  87. 		int g=-1;
  88. 		for(int j=i+1;j<=n;++j)
  89. 		{
  90. 			g+=hsh(i+1,j-1)==hshf(i+1,j-1);
  91. 			ans+=g*wo[i][j];
  92. 		}
  93. 	}
  94. 	for(int i=n;i>=1;--i)
  95. 	{
  96. 		int g=-1;
  97. 		for(int j=i-1;j>=1;--j)
  98. 		{
  99. 			g+=hsh(j+1,i-1)==hshf(j+1,i-1);
  100. 			ans+=g*wo[j][i];
  101. 		}
  102. 	}
  103. 	cout<<ans<<"\n";
  104. }
Success #stdin #stdout 0s 21464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/a0Qth5
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!