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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#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; } |