Я пытаюсь решить эту проблему в spoj
Мне нужно найти количество поворотов данной строки, которое сделает ее лексикографически наименьшей среди всех поворотов.
Например:
Оригинал: ama
Первый поворот: maa
Второй поворот: aam
Это наименьшее лексикографическое вращение, поэтому ответ - 2.
Вот мой код:
string s,tmp;
char ss[100002];
scanf("%s",ss);
s=ss;
tmp=s;
int i,len=s.size(),ans=0,t=0;
for(i=0;i<len;i++)
{
string x=s.substr(i,len-i)+s.substr(0,i);
if(x<tmp)
{
tmp=x;
t=ans;
}
ans++;
}
cout<<t<<endl;
Я получаю сообщение «Превышен лимит времени» для этого решения. Я не понимаю, какие оптимизации можно сделать. Как я могу увеличить скорость моего решения?