fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string s;int n;
  5. bool cmp_init(int a, int b)
  6. {
  7. 	return s[a]<s[b] || (s[a]==s[b] && a<b);
  8. }
  9.  
  10. int jmp;
  11. vector<int> pos;
  12. bool cmp(int a, int b)
  13. {
  14. 	return pos[a]<pos[b] || (pos[a]==pos[b] && pos[(a+jmp)%n]<pos[(b+jmp)%n]);
  15. }
  16.  
  17. int main() {
  18. 	int tc;cin>>tc;
  19. 	while(tc--){
  20. 	cin>>s;
  21. 	int m=s.size();
  22. 	s=s+s+"{";
  23. 	n=s.size();
  24.  
  25. 	vector<int> SA(n,0);
  26. 	for(int i=0;i<n;i++)SA[i]=i;
  27. 	sort(SA.begin(), SA.end(), cmp_init);
  28. 	pos.assign(n,0);
  29.  
  30. 	for(int i=1 , c=0;i<n;i++)pos[SA[i]]=(s[SA[i]]==s[SA[i-1]])?c:++c;
  31.  
  32. 	for(jmp=1;jmp<=n;jmp*=2)
  33. 	{
  34.  
  35. 		sort(SA.begin(), SA.end(), cmp);
  36.  
  37. 		vector<int> tmp(n,0);
  38.  
  39. 	    for(int i=1 , c=0;i<n;i++)tmp[SA[i]]=(pos[SA[i]]==pos[SA[i-1]] && pos[(SA[i]+jmp)%n]==pos[(SA[i-1]+jmp)%n])?c:++c;
  40.  
  41. 		for(int i=0;i<n;i++)pos[i]=tmp[i];
  42.  
  43. 	}
  44.  
  45. 		for(int i=0;i<n;i++)if(SA[i]<m){cout<<SA[i]+1<<"\n";break;}
  46. 	}
  47.  
  48. }
Time limit exceeded #stdin #stdout 5s 19888KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ziyiOI
BEADS
language:
C++14 (gcc 8.3)
created:
4 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!