fork download
copy 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. using namespace std;
  6. #define MAX 50005
  7. string s;
  8. int n,stp;
  9. int SA[MAX],iSA[MAX],LCP[MAX],temp[MAX]={0};
  10. bool cmp(int i,int j)
  11. {
  12. 	if(iSA[i]!=iSA[j])
  13.  	return iSA[i]<iSA[j];
  14. 	i+=stp;	
  15. 	j+=stp;
  16. 	return (i<n && j<n)?(iSA[i]<iSA[j]):i>j; 
  17. }
  18. void constructSA()
  19. {
  20. 	n=s.length();
  21. 	for(int i=0;i<n;i++)
  22. 	{
  23. 		SA[i]=i;
  24. 		iSA[i]=(int)s[i];
  25. 	}
  26. 	memset(temp,0,sizeof temp);
  27. 	for(stp=1;;stp*=2)
  28. 	{
  29. 		sort(SA,SA+n,cmp);
  30. 		for(int i=0;i<n-1;i++)
  31. 		temp[i+1]=temp[i]+cmp(SA[i],SA[i+1]);	
  32. 		for(int i=0;i<n;i++)
  33. 		{
  34. 			iSA[SA[i]]=temp[i];
  35. 		}
  36. 		if(temp[n-1]==n-1)
  37. 		break;
  38. 	}
  39.  
  40. }
  41. void constructLCP()
  42. {
  43. 	for(int i=0,k=0;i<n;i++)
  44. 	{
  45. 		if(iSA[i]!=n-1)
  46. 		{
  47. 			int j=SA[iSA[i]+1];
  48. 			while(s[i+k]==s[j+k])
  49. 			k++;
  50. 			LCP[iSA[i]]=k;
  51. 			if(k>0)
  52. 			k--;
  53. 		}
  54. 	}
  55. }
  56. int main()
  57. {
  58. 	int t;
  59. 	cin>>t;
  60. 	while(t--)	
  61. 	{
  62. 		int ans=0;
  63. 		cin>>s;
  64. 		constructSA();
  65. 		constructLCP();
  66. 		for(int i=0;i<n;i++)
  67. 		ans+=LCP[i];
  68. 		cout<<((n*(n+1))/2)-ans<<endl;
  69. 		/*memset(SA,0,sizeof SA);*/
  70. 		memset(iSA,0,sizeof iSA);
  71. 		memset(LCP,0,sizeof LCP);
  72. 		memset(temp,0,sizeof temp);
  73. 	}
  74. }
Success #stdin #stdout 0s 3648KB
comments (?)
stdin
copy 
2
CCCCC
ABABA
stdout
copy 
5
9
https://ideone.com/fVhCSG
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!