fork download
copy 
  1. #include <stdio.h>
  2. #include <map>
  3. #include <string.h>
  4. #include <string>
  5. #include <algorithm>
  6. using namespace std;
  7. typedef long long ll;
  8. #define mod 1000000007
  9. #define v 2
  10. ll hash[10005];
  11. bool ispalindrome[10005][10005];
  12. ll mod_inverse[10005];
  13. char str[10005];
  14. ll modpow(ll x,ll n)
  15. {
  16. 	ll res=1;
  17. 	while(n)
  18. 	{
  19. 		if(n&1) res = res*x%mod;
  20. 		x = x*x%mod;
  21. 		n >>= 1;
  22. 	}
  23. 	return res;
  24. }
  25. ll calc(int l,int r)
  26. {
  27. 	if(l==1) return hash[r];
  28. 	ll d = (hash[r]-hash[l-1]+mod)%mod;
  29. 	return d*mod_inverse[l]%mod;
  30. }
  31. int main()
  32. {
  33. 	scanf("%s",str);
  34. 	int n=strlen(str);
  35. 	for(int i=n;i>=1;i--) str[i] = str[i-1];
  36. 	for(int i=1;i<=n;i++) ispalindrome[i][i]=true;
  37. 	for(int i=1;i<n;i++) ispalindrome[i][i+1] = str[i]==str[i+1];
  38. 	for(int len=3;len<=n;len++)
  39. 	{
  40. 		for(int i=1;i+len-1<=n;i++)
  41. 		{
  42. 			ispalindrome[i][i+len-1] = ispalindrome[i+1][i+len-2] & (str[i] == str[i+len-1]);
  43. 		}
  44. 	}
  45. 	ll cur = 1LL;
  46. 	for(int i=1;i<=10005;i++)
  47. 	{
  48. 		mod_inverse[i] = modpow(cur,mod-2); cur=cur*v%mod;
  49. 	}
  50. 	cur = 1LL;
  51. 	for(int i=1;i<=n;i++)
  52. 	{
  53. 		hash[i] = (hash[i-1]+cur*(str[i]-'a')%mod)%mod;
  54. 		cur = cur*v%mod;
  55. 	}
  56. 	int res=0;
  57. 	for(int i=1;i<=n;i++)
  58. 	{
  59. 		map<ll,int>ch; int maxvalue=0;
  60. 		for(int j=1;j+i-1<=n;j++)
  61. 		{
  62. 			if(ispalindrome[j][j+i-1]) maxvalue = max(maxvalue,++ch[calc(j,j+i-1)]);
  63. 		}
  64. 		res = max(res,maxvalue*i);
  65. 	}
  66. 	printf("%d%c",res,10);
  67. }
Success #stdin #stdout 0.01s 101376KB
comments (?)
stdin
copy 
abacabacaba
stdout
copy 
14
https://ideone.com/vBb2Jy
language:
C++ (gcc 8.3)
created:
10 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!