Нахождение лексикографически самых больших вращений в строке

Вы можете просто:
1. генерировать вращения
2. положить все повороты на карте<>
3. найти последний элемент карты.
Вот реализация в C ++.

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

int main() {
// your code goes here
string str;int len,i=0,j=0,k=0;char temp;
cin>>str;
len = str.length();
map<string,int>m;
while(i<len)
{
temp = str[0];
while(j<len-1)
{
str[j] = str[j+1];
j++;
}
str[j] = temp;
m[str] = k;
k++;
i++;j=0;
}
str = m.rbegin()->first;
cout<<str;
return 0;
}

Эту проблему можно решить за O (n log n), добавив сначала строку к себе и построив из нее массив суффиксов. Найдите соответствующую запись и получите желаемый результат. Реализация оставлена ​​как упражнение.

//Here the index with greater value is selected,
//if the same char occurs again the next characters
// of prev and curr characters is checked:-Prev=maxIndex,curr=i
#include<bits/stdc++.h>
using namespace std;
int getIndex(char *str){
int max=INT_MIN,maxIndex;
int n=strlen(str);
int j,p;
for(int i=0;i<n;i++)
{
if(str[i]>max)
{
max=str[i];
maxIndex=i;
}
else if(str[i]==max)
{
j=maxIndex+1;
p=(i+1)%n;
while(j<n && p<n && str[j]==str[p]){
j++;
p=(p+1)%n;
}
maxIndex=str[p]>str[j]?i:maxIndex;
}
}
return maxIndex;
}
int main(void)
{
char str[4000008];
scanf("%s",str);
int i=getIndex(str);
for(int j=i;j<strlen(str);j++)
cout<<str[j];
for(int j=0;j<i;j++)
cout<<str[j];}

Ваш алгоритм, исправленный, сводится к:

1. Установить текущее наилучшее вращение на единицу (начало повернутой строки — текущий индекс 0).
2. Для каждого возможного вращения (все остальные стартовые индексы):
   1. Сравните с текущим лучшим вращением с чем-то вроде wrapcmp ниже.
   2. Установите текущий лучший поворот, если у нас был лучший кандидат.

Сложность времени: O (n * n)
Пространство-Сложность: на месте

// Function to do ordinal-comparison on two rotations of a buffer
// buffer: The buffer containing the string
// n: The buffers size (string-length)
// a: Index where the first buffer starts pre-rotation
// b: Index where the second buffer starts pre-rotation
int wrapcmp(const void* buffer, size_t n, size_t a, size_t b) {
auto x = (const unsigned char*)buffer;
auto m = n - std::max(a, b);
int ret = memcmp(x+a, x+b, m);
if(ret) return ret;
auto left = n - m;
a = (a + m) % n;
b = (b + m) % n;
m = left - std::max(a, b);
ret = memcmp(x+a, x+b, m);
if(ret) return ret;
a = (a + m) % n;
b = (b + m) % n;
return memcmp(x+a, x+b, left - m);
}

Используется на колирус: http://coliru.stacked-crooked.com/a/4b138a6394483447
Помещение в общий алгоритм оставлено в качестве упражнения для читателя.

Это было слишком заманчиво, так что я могу также опубликовать свои усилия. Не уверен, как это оценивает эффективность Wize. Кажется, работает, насколько я тестировал:

#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

std::string max_rot(const std::string& s)
{
std::string tmp;
std::string max;

std::string::const_iterator m = std::max_element(s.begin(), s.end());
if(m != s.end())
for(char c = *m; (m = std::find(m, s.end(), c)) != s.end(); ++m)
if(max < tmp.assign(m, s.end()).append(s.begin(), m))
max = tmp;

return max;
}int main()
{
size_t times = 0;
std::string text;

do { std::cout << "\nHow many words? : "; }
while(std::getline(std::cin, text) && !(std::istringstream(text) >> times));

std::vector<std::string> words;
while(times-- && (std::cin >> text))
words.push_back(text);

for(const auto& s: words)
std::cout << max_rot(s) << '\n';

}

В порядке объяснения. Он находит самое высокое символьное значение в строке и поворачивает строку, чтобы сделать этот символ первым. Если затем ищет повторяющиеся старшие символы в оставшейся части строки, отслеживая самую высокую попытку. Там может быть место для оптимизации.

Эта задача используется в активном конкурсе, я не прошу ответа до 18 сентября в 21:00 по IST. Поскольку код видим, нам, возможно, придется запретить пользователю участвовать в любом из наших конкурсов.