poly.cpp

#include <fstream>
#include <vector>
#include <strings.h>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ifstream fr("input.txt");
    ofstream fw("output.txt");

    string s;
    fr >> s;

    string s1 = s;
    reverse(s1.begin(), s1.end());

    string t = s1 + "#" + s;

    int max_num = 0;

    int size = t.size();

    int arrPref[size];
    arrPref[0] = 0;

    int k = 0;

    for (int q = 1; q < size; q++) {
        k = arrPref[q - 1];
        while (k > 0 && t[k] != t[q]) {
            k = arrPref[k - 1];
        }

        if (t[q] == t[k]) {
            k++;
        }

        arrPref[q] = k;
        if (k > max_num) {
            max_num = k;
        }
    }

    if (max_num == s1.length()) {
        fw << "";
    }
    else {
        s = s1.substr(max_num);
        fw << s;
    }

    fr.close();
    fw.close();

    return 0;
}