Pomoc z zadaniem maturalnym - palindromy

0

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.

0

Trochę „przesadzone” rozwiązanie; bardziej na rozmowę kwalifikacyjną niż maturę, bo na maturze powolność rozwiązania to nie problem.

Dla danego słowa w:

  1. Wyznacz najdłuższy prefiks w będący palindromem, oznacz ten palindrom jako w1:
  • zdefiniuj sobie funkcję pomocniczą liczącą sumę kontrolną rozszerzającą dla podstringów
  • idąc od końca, licz kolejno te sumy dla coraz krótszych prefiksów
  • jak będzie taka sama, to sprawdź dla pewności, czy to nie przypadkowa kolizja (porównaj prefiks czytany od lewej do prawej z tym od prawej do lewej); jeśli nie, to właśnie znalazłeś w1
  1. Podziel w tak, by w = w1 + w2.
  2. Zwróć w2.odTyłu() + w.
0
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.

0

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;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1