fork(1) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <map>
  4. #include <set>
  5. #include <functional>
  6. #include <vector>
  7. #include <cstring>
  8. #include <cstdlib>
  9. #include <math.h>
  10. using namespace std;
  11. #define rep(i,n) for(int (i)=(0);(i)<(n);(i)++)
  12. #define repn(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
  13. #define pb push_back
  14. #define mp make_pair
  15. typedef pair<int,int> pii;
  16. typedef pair<int,pii> pip;
  17. #define fi first
  18. #define se second
  19. typedef long long ll;
  20.  
  21. char s[300010];
  22. char tmp[600020];
  23. int rad[600020];
  24. int N;
  25.  
  26. void manacher()
  27. {
  28. 	rep(i,N*2+1)tmp[i]='#';
  29. 	rep(i,N)tmp[i*2+1]=s[i];
  30. 	int i=0,j=0;
  31. 	int n=N*2+1;
  32. 	for(int i=0;i<n;)
  33. 	{
  34. 			while(i-j>=0&&i+j<n&&tmp[i-j]==tmp[i+j])j++;
  35. 			rad[i]=j;
  36. 			int k=1;
  37. 			while(rad[i-k]<rad[i]-k)rad[i+k]=rad[i-k],k++;
  38. 			i+=k;
  39. 			j=max(0,j-k);
  40. 	}
  41. }
  42. int sa[300001],ra[300001],sak;
  43. int ti[300001];
  44. int lcp[300001];
  45. bool cmp_sa(int a,int b)
  46. {
  47. 	if(ra[a]!=ra[b])return ra[a]<ra[b];
  48. 	int cha=(a+sak<=N)?ra[a+sak]:-1;
  49. 	int chb=(b+sak<=N)?ra[b+sak]:-1;
  50. 	return cha<chb;
  51. }
  52. void construct_sa(int n)
  53. {
  54. 	rep(i,n+1)
  55. 	{
  56. 		sa[i]=i;
  57. 		ra[i]=(i<n)?s[i]:-1;
  58. 	}
  59. 	for(sak=1;sak<n;sak*=2)
  60. 	{
  61. 		sort(sa,sa+n+1,cmp_sa);
  62. 		ti[sa[0]]=0;
  63. 		for(int i=1;i<=n;i++)ti[sa[i]]=ti[sa[i-1]]+cmp_sa(sa[i-1],sa[i]);
  64. 		rep(i,n+1)ra[i]=ti[i];
  65. 	}
  66. }
  67. void construct_lcp(int n)
  68. {
  69. 	rep(i,n+1)ti[sa[i]]=i;
  70. 	int h=0;
  71. 	rep(i,n)
  72. 	{
  73. 		int j=sa[ti[i]-1];
  74. 		if(h>0)h--;
  75. 		while(i+h<n&&j+h<n&&s[i+h]==s[j+h])h++;
  76. 		lcp[ti[i]]=h;
  77. 	}
  78. }
  79. struct UnionFind
  80. {
  81. 	int par[300001],ra[300001],sz[300001];
  82. 	void init(){rep(i,300001)par[i]=i,ra[i]=0,sz[i]=0;}
  83. 	int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
  84. 	bool same(int a,int b){return find(a)==find(b);}
  85. 	void unite(int a,int b){if((a=find(a))!=(b=find(b))){if(ra[a]<ra[b])swap(ra[a],ra[b]);sz[a]+=sz[b];par[b]=a,ra[a]+=ra[a]==ra[b];}}
  86. } uf;
  87.  
  88. int main()
  89. {
  90. 	FILE *in,*out;
  91.  
  92. 	in=stdin;out=stdout;
  93. 	// in APIO 2014
  94. 	//in=fopen("palindrome.in","r");
  95. 	//out=fopen("palindrome.out","w");
  96.  
  97. 	fscanf(in,"%s",&s);
  98. 	ll ans=0;
  99. 	N=strlen(s);
  100. 	manacher();
  101. 	construct_sa(N);
  102. 	construct_lcp(N);
  103. 	vector<pip> lun;
  104. 	repn(i,1,N+1)lun.pb(mp(lcp[i],mp(sa[i-1],sa[i])));
  105. 	sort(lun.begin(),lun.end(),greater<pip>());
  106. 	//odd
  107. 	uf.init();
  108. 	vector<pii> aq;
  109. 	rep(i,N)aq.pb(mp(rad[i*2+1]/2,i));
  110. 	sort(aq.begin(),aq.end(),greater<pii>());
  111. 	int ptr=0;
  112. 	rep(i,N)
  113. 	{
  114. 		while(ptr<N&&lun[ptr].fi>=aq[i].fi)
  115. 		{
  116. 			uf.unite(lun[ptr].second.first,lun[ptr].second.second);
  117. 			ptr++;
  118. 		}
  119. 		int ppuf=uf.find(aq[i].se);
  120. 		uf.sz[ppuf]++;
  121. 		ans=max(ans,ll(uf.sz[ppuf])*(aq[i].first*2-1));
  122. 	}
  123.  
  124. 	//even
  125. 	uf.init();
  126. 	aq.clear();
  127. 	rep(i,N)aq.pb(mp(rad[i*2]/2,i));
  128. 	sort(aq.begin(),aq.end(),greater<pii>());
  129. 	ptr=0;
  130. 	rep(i,N)
  131. 	{
  132. 		while(ptr<N&&lun[ptr].fi>=aq[i].fi)
  133. 		{
  134. 			uf.unite(lun[ptr].second.first,lun[ptr].second.second);
  135. 			ptr++;
  136. 		}
  137. 		int ppuf=uf.find(aq[i].se);
  138. 		uf.sz[ppuf]++;
  139. 		ans=max(ans,ll(uf.sz[ppuf])*(aq[i].first*2));
  140. 	}
  141.  
  142. 	fprintf(out,"%lld\n",ans);
  143. 	fclose(in);fclose(out);
  144. }
Success #stdin #stdout 0s 14864KB
comments (?)
stdin
copy 
aaaaaabcbcba
stdout
copy 
12
https://ideone.com/WSRCV5
language:
C++ (gcc 8.3)
created:
9 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!