Матч 335, Палиндромизация (Palindromize)

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

Палиндромом называется строка, которая читается одинаково слева направо и справа налево. К концу заданного слова следует дописать наименьшее количество букв (или ничего не дописывать) так, чтобы полученное слово стало палиндромом.

Класс: Palindromize

Метод: string minAdds(string s)

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

Вход. Строка из прописных букв латинского алфавита.

Выход. Строка-палиндром наименьшей длины, префиксом которой является входное слово.

Пример входа

s

“add”

“cigartragic”

“redocpot”

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

“adda”

“cigartragic”

“redocpotopcoder”

РЕШЕНИЕ

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

Функция isPalindrom(s) проверяет, является ли слово s палиндромом. Перебираем подстроки s1 строки s с 0 до i - го символа (i = 0, 1, 2, …, |s|), обращаем их. Находим наименьшее i, для которого строка s + reverse(s1) будет палиндромом.

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#include <string>

using namespace std;

int isPalindrom(string s)

{

int i, n = s.size();

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

if (s[i] != s[n - 1 - i]) return 0;

return 1;

}

class Palindromize

{

public:

string minAdds(string s)

{

int i;

string s1;

for(i = 0; i <= s.size(); i++)

{

s1 = s.substr(0,i);

reverse(s1.begin(),s1.end());

if (isPalindrom(s + s1)) return s + s1;

}

}

};