Witajcie.
Przygotowuję się do matury z informatyki i próbuję rozwiązywać arkusze z poprzednich lat. Z jednym z nich mam niestety problem, nie wiem jak się zabrać za część zadania.
W załączniku zamieszczam opis części zadania z którą sobie nie radzę. Mam nadzieję że będziecie mieć jakiś pomysł i pomożecie mi uzyskać rozwiązanie.
Trochę „przesadzone” rozwiązanie; bardziej na rozmowę kwalifikacyjną niż maturę, bo na maturze powolność rozwiązania to nie problem.
Dla danego słowa w:
w będący palindromem, oznacz ten palindrom jako w1:w1w tak, by w = w1 + w2.w2.odTyłu() + w.
string given - całe słowo
string code(string) - funkcja odwracająca słowo, zakładam, że masz ją, bo była potrzebna w a)
void Passwords::make_palindrom()
{
int i = given.size() - 1;
while (given.substr(0, i) != code(given.substr(0, i)))
{
i--; //dekrementacja i, aż do momentu, gdy substring kończący się na i, jest równy zakodowanemu substringowi, kończącemu się na i
}
palindrom = given.substr(0, i); //najdłuższy palindrom w słowie
p_length = i; //długość tego palindromu
}
{
rest = given.substr(p_length, (given.size() - p_length)); //szukasz substringu, zaczynającego się tam, gdzie kończy się najdłuższy palindrom
pass = code(rest);
pass += palindrom;
pass += rest;
}
W taki sposób ja to robiłem, jak masz pytania to wal śmiało.
Moja propozycja
#include <iostream>
using namespace std;
int left_palindrome_length(string v) {
int i = 0, j = v.length() - 1;
while(i < j) {
if(v[i] == v[j]) {
i++;
j--;
} else {
i = 0;
j--;
}
}
return 2 * i + (i == j);
}
string f(string v) {
int i = 0, j = 0;
string r = "";
int lpl = left_palindrome_length(v);
r.append(v.rbegin(), v.rbegin() + (v.length() - lpl));
r.append(v);
return r;
}
int main()
{
string words[] = {"kajak", "kajakarstwo", "mama", "kaktus", "wanna", "egzamin", "w", "ww", "ab", "", "aAa", "aAA", "aBbA"};
for(string s: words)
cout << f(s) << endl;
}
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.