Aby sprawdzić czy napis jest palindromem, wystarczy porównywać znaki z początku i końca napisu aż do momentu gdy indeksy się zrównają.
Teraz wystarczy zauważyć że operacje indeksowania powinny być wykonywane z:
1. Przesunięciem o k
2. Modulo długość napisu.
Przy takich operacjach przydaje się trick z dodaniem samej wartości modulo by uniknąć wartości ujemnych. Czyli pseudo-kod wyliczenia indeksu będzie wyglądał tak:
indeks_dostepu = (indeks + msg.size() + k) % msg.size()
#include <iostream>
#include <string>
#include <iomanip>
#include <cstddef>
bool is_palindrome(const std::string& msg, std::size_t k = 0) {
auto last_idx = msg.size() - 1;
std::size_t first_idx = 0;
while (first_idx != last_idx) {
auto f_idx = (first_idx + msg.size() + k) % msg.size();
auto l_idx = (last_idx + msg.size() + k) % msg.size();
if (msg[f_idx] != msg[l_idx]) {
return false;
}
++first_idx;
--last_idx;
}
return true;
}
int main() {
std::string msg = "akkaj";
std::cout << msg << " is palindrome? " << std::boolalpha << is_palindrome(msg, 2) << '\n';
}
Na koniec wystarczy spostrzec że sprawdzenie "zwykłego palindromu" to sprawdzenie napisu z przesunięciem 0.
Takie podejście oczywiście ma wadę/konsekwencje. Nie będzie działało dla napisów które będą dłuższe od std::size_t / 2. Nie sądzę jednak by to było tu istotne ograniczenie.
Alternatywnym rozwiązaniem jest bazujące na iteratorach, algorytmie std::rotate i std::equal.
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cstddef>
bool is_palindrome(const std::string& msg, std::size_t k = 0) {
std::string msg_data = msg;
std::rotate(msg_data.begin(), msg_data.begin() + k, msg_data.end());
return std::equal(msg_data.begin(), msg_data.begin() + msg_data.size() / 2, msg_data.rbegin());
}
int main() {
std::string msg = "akkaj";
std::cout << msg << " is palindrome? " << std::boolalpha << is_palindrome(msg, 2) << '\n';
}