fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27.  
  28. int len;
  29. char a[MAX];
  30. int L[MAX],pre[MAX],suf[MAX];
  31. int num[MAX],diff=1;
  32.  
  33. int cmp(int a,int b)
  34. {
  35. 	return L[a]<L[b];
  36. }
  37.  
  38. void del(int u)
  39. {
  40. 	if(pre[u]!=-1)
  41. 		suf[pre[u]]=suf[u];
  42. 	if(suf[u]!=len)
  43. 		pre[suf[u]]=pre[u];
  44. 	diff=max(diff,suf[u]-pre[u]);
  45. }
  46.  
  47. int main()
  48. {
  49. //	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  50. 	int i;
  51. 	scanf("%s",a);
  52. 	len=strlen(a);
  53. 	L[0]=0;
  54. 	int last=0;
  55. 	for(i=0;i<len;++i)
  56. 	{
  57. 		L[i]=-1;
  58. 		if(last+L[last]>=i && L[last]!=-1)
  59. 			L[i]=min(last+L[last]-i,L[i-last]);
  60. 		for(;i+L[i]+1<len && a[ i+L[i]+1 ] == a[ L[i] + 1 ];++L[i])
  61. 			;
  62. 		if(i+L[i]>last+L[last] || last==0)
  63. 			last=i;
  64. 		pre[i]=i-1;
  65. 		suf[i]=i+1;
  66. 		num[i]=i;
  67. 	}
  68. 	sort(num,num+len,cmp);
  69. 	for(i=0;i<len;)
  70. 	{
  71. 		int x=L[num[i]];
  72. 		if(x!=-1 && diff<=x+1)
  73. 		{
  74. 			cout<<x+1<<endl;
  75. 			break;
  76. 		}
  77. 		for(;i<len && L[num[i]]==x;++i)
  78. 			del(num[i]);
  79. 	}
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0s 19904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l2uHwF
language:
C++ (gcc 8.3)
created:
10 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!