#include <iostream>
#include <random>
#include <time.h>
// Условие б) Паліндромом вважається будь-який набір символів,
симетричний відносно своєї середини.
Рядок задається користувачем з клавіатури або програмно (якщо
користувач ввів порожній рядок).
Даний рядок перетворити на паліндром двома способами,
дозволивши користувачу вибрати один з них: – довжина утвореного рядка, який є паліндромом, повинна бути
мінімальною; – вивести на екран всі паліндроми, які можна утворити з даного
рядка.
Вибір режиму реалізувати у вигляді меню, передбачивши
повторення дій необхідну кількість разів. Серед режимів роботи
програми передбачити перевірку введеного рядка на те, чи є він
паліндромом, та вихід з програми.
using namespace std;

int palindromTest(string str, int mid, int len, int plus = 0) {
    for (int i = mid + plus; i < len; i++) {
        int left = mid - abs(mid - i - 1 + plus);
        if (left == 0 && str[i] == str[left]) {
            return i;
        }
        if (i == len - 1 && str[i] == str[left]) {
            return left;
        }

        if (str[i] != str[left]) {
            return 0;
        }
    }
    return -1;
}

string fullPal(string str, int mid, int shift) {
    int len = str.length();
    string new_str;
    if ((mid == shift && shift == 0) || shift > mid) {
        new_str = "";
        for (int i = len - 1; i > shift; i--) {
            new_str += str[i];
        }
        new_str += str;
    }
    if ((mid == shift && shift == len - 1) || shift < mid) {
        new_str = str;
        for (int i = shift - 1; i >= 0; i--) {
            new_str += str[i];
        }
    }
    return new_str;
}

bool existEl(string arr[], string str, int size) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == str)
            return true;
    }
    return false;
}

int main() {
    string str;
    char str1[255] = "";
    string alph = "abcdefghijklmnopqrstuvwxyz";
    cout << "Write line:" << endl;
    cin.getline(str1, 255);

    str = str1;
//    str = "1234";
    srand(time(NULL));
    if (str == " ") {
        str = "";
        int ran = rand() % 15 + 1;
        for (int i = 0; i < ran; i++) {
            int alpha = rand() % 25;
            str += alph[alpha];
        }
    }
    int len = str.length();
    int ans;
    cout << "Write 1 for first method, 2 for second method, 3 to check palindrom or 1 to exit" << endl;
    int min = 100000;
    string arr[len + 2];
    int iter = 0;
    if (len <= 2) {
        if (str[0] == str[1] || len == 1) {
            arr[0] = str;
            iter++;
            min = 2;
        } else {
            arr[0] = str + str[0];
            arr[1] = str[1] + str;
            iter += 2;
            min = 3;
        }
    } else {
        min = 100000;
        for (int i = 1; i < len - 1; i++) {

            int a = palindromTest(str, i, len);
            int b = palindromTest(str, i, len, 1);
            if (a != 0) {
//                cout << str << ' ' << i << ' ' << a << endl;
                arr[iter] = fullPal(str, i, a);
                if (arr[iter].length() < min)
                    min = arr[iter].length();
                iter++;
            }
            if (b != 0) {
//                cout << str << ' ' << i << ' ' << b << endl;
                arr[iter] = fullPal(str, i, b);
                if (arr[iter].length() < min)
                    min = arr[iter].length();
                iter++;
            }

        }
        if (!existEl(arr, str, iter)) {
            arr[iter++] = fullPal(str, 0, 0);
            arr[iter++] = fullPal(str, len - 1, len - 1);
        }
        while (true) {
            cin >> ans;
            if (ans == 1) {
                for (int i = 0; i < iter; i++) {
                    if (arr[i].length() == min)
                        cout << arr[i] << endl;
                }
            }
            if (ans == 2) {
                for (int i = 0; i < iter; i++) {
                    cout << arr[i] << endl;
                }
            }
            if (ans == 3) {
                if (existEl(arr, str, iter))
                    cout << "It's a palindrome" << endl;
                else {
                    cout << "It's not a palindrome" << endl;
                }

            }
            if (ans == 4)
                break;
        }
    }

    for (int i = 0; i < iter; i++) {
        cout << arr[i] << ' ';
    }

    return 0;
}