Как найти набор различных строк из заданной строки после циклических сдвигов?

Question

Я решаю [ВОПРОС] [1] в Codeforces, где оператор проблемы просит меня найти набор всех различных строк из заданной строки после циклических сдвигов. , как, например: данной строки: "abcd" вывод должен быть 4 ("dabc", "cdab", "bcda", "abcd") [примечание: "abcd" также считается]

Так

t=s[l-1]; 

for(i=l-1;i>0;i--) 
{ 
    s[i]=s[i-1]; 
} 

s[0]=t; 

я применил выше способу length - 1 раз для всех возможных строк, но я не могу найти отличительные,
есть ли функция STL для этого?

Answer 1

Не уверен в специфических функциях STL, однако общим решением может быть наличие всех сдвинутых строк в списке. Затем вы сортируете список, а затем перебираете элементы списка. Когда текущий элемент отличается от последнего, увеличивайте счетчик.

Возможно, существует решение, которое менее интенсивно использует память. Для коротких строк это решение должно быть достаточным.

Answer 2

Вы можете использовать вектор для создания списка после поворота с помощью vector.push_back ("string"). Перед каждым нажатием, Вы можете проверить, если он уже существует, используя что-то вроде:

if (std::find(vector.begin(), vector.end(), "string") != v.end()) 
{ 
increment++; 
vector.push_back("string"); 
} 

Или же вы можете рассчитывать элементы в конце от vector.size(); и удалить increment ++.

Надеется, что это помогает

Answer 3

Вы можете использовать следующее:

std::set<std::string> 
retrieve_unique_rotations(std::string s) 
{ 
    std::set<std::string> res; 

    res.insert(s); 
    if (s.empty()) { 
     return res; 
    } 
    for (std::size_t i = 0, size = s.size() - 1; i != size; ++i) { 
     std::rotate(s.begin(), s.begin() + 1, s.end()); 
     res.insert(s); 
    } 
    return res; 
} 

Demo