719

The solution solves the problem within time limit but there are better solutions, by sorting the array using counting sort might give a better timing.

There is also a solution without using a suffix array , simply by adding the string with itself and comparing which one is the lowest sub string.

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;
string str;

struct node{
	int fst,ed,idx;
}arr[20005];

int L[30][20005];

bool cmp(node a,node b)
{
	return ( (a.fst==b.fst)?(a.ed<b.ed):(a.fst<b.fst) );
}
void makesa()
{
	int len = str.size();
	int stp=1;
	for(int i=0;i<str.size();i++)
		L[0][i]=str[i]-'a';
	for(int cnt=1;cnt/2<len;cnt<<=1,stp++)
	{
		for(int i=0;i<len;i++)
		{
			arr[i].fst = L[stp-1][i];
			arr[i].ed = (i+cnt)<len?L[stp-1][i+cnt]:-1;
			arr[i].idx = i;
		}
		sort(arr,arr+len,cmp);
		for(int i=0;i<len;i++)
			L[stp][arr[i].idx]= ( (i>0 && arr[i-1].fst==arr[i].fst && arr[i-1].ed==arr[i].ed)?L[stp][arr[i-1].idx]:i );
	}
}
int main()
{
	scanf("%d",&n);
	string s;
	while(n--)
	{
		cin>>s;
		str=s;
		str.append(s);
		str.append(1u,'~');
		makesa();
		printf("%d\n",arr[0].idx+1);
	}
	return 0;
}