Матч 358, Циклические слова (CyclicWords)

Дивизион 2, Уровень 1

Слово называется циклическим, если его записать по кругу (первая и последняя буквы находятся рядом). Для представления циклического слова можно выбрать произвольную позицию и прочитать его по часовой стрелке. Например, “picture” и “turepic” представляют одно и то же слово.

Массив words содержит набор циклических слов. Необходимо найти количество разных слов, которые они представляют.

Класс: CyclicWords

Метод: int differentCW(vector<string> words)

Ограничения: words содержит от 1 до 50 элементов ‘a’ – ‘z’.

Вход. Массив words, содержащий набор циклических слов.

Выход. Количество разных слов, которые представляют циклические слова в массиве words.

Пример входа

words

{ "picture", "turepic", "icturep", "word", "ordw" }

{ "ast", "ats", "tas", "tsa", "sat", "sta", "ttt" }

{"aaaa", "aaa", "aa", "aaaa", "aaaaa"}

Пример выхода

2

3

4

РЕШЕНИЕ

обработка строк

Нормализацией циклического слова будем называть лексикографически наименьшее слово, которое его может представлять. Функция normalize(s) находит такое лексикографически наименьшее представление. Для каждого слова массива words находим его нормализованное представление, которое и заносим в множество s. По окончанию обработки входного массива количество элементов множества s равно числу разных слов.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <vector>

#include <set>

using namespace std;

set<string> s;

string normalize(string s)

{

int i, n = s.size();

string res = s; s = s + s;

for(i = 0; i < n; i++)

if (s.substr(i,n) < res) res = s.substr(i,n);

return res;

}

class CyclicWords

{

public:

int differentCW(vector<string> words)

{

for(int i = 0; i < words.size(); i++)

s.insert(normalize(words[i]));

return s.size();

}

};