1635

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string s;

long long n = 4002, p;

vector <pair <int, int>> u(n);
vector <long long> paw(n), h(n), rh(n), evenCount(n), oddCount(n), r({ 10000, 0 });
vector <vector <long long>> dp(n, r);

long long getHash(int L, int R) {
    long result = h[R];
    if (L > 0) result -= h[L - 1];
    return result;
}

long long getRevHash(int L, int R) {
    long result = rh[L];
    if (R < n - 1) result -= rh[R + 1];
    return result;
}

void rek(int prev, int tek) {
    if (tek != 0) {
        rek(tek, dp[tek][1]);
    }

    for (int i = tek; i < prev; i++) {
        cout << s[i];
    }

    cout << " ";
}

bool isPalindrome(int L, int R) {
    return getHash(L, R) * paw[n - R - 1] == getRevHash(L, R) * paw[L];
}

int main()
{
    iostream::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> s;
    n = s.size(), p = 31;



    paw[0] = 1;
    for (int i = 1; i < n; i++) {
        paw[i] = paw[i - 1] * p;
    }

    h[0] = s[0];
    for (int i = 1; i < n; i++) {
        h[i] = h[i - 1] + paw[i] * s[i];
    }

    rh[n - 1] = s[n - 1];
    for (int i = n - 2, j = 1; i >= 0; i--, j++) {
        rh[i] = rh[i + 1] + paw[j] * s[i];
    }

    for (long long i = 0; i < (n - 1); i++) {
        int left = 0, right = min(i + 1, n - i - 1);
        while (left < right) {
            int middle = (left + right) / 2;
            if (isPalindrome(i - middle, i + middle + 1)) {
                evenCount[i] = middle + 1;
                left = middle + 1;
            }
            else {
                right = middle;
            }
        }
    }

    for (long long i = 0; i < n; i++) {
        int left = 0, right = min(i + 1, n - i);
        while (left < right) {
            int middle = (left + right) / 2;
            if (isPalindrome(i - middle, i + middle)) {
                oddCount[i] = middle;
                left = middle + 1;
            }
            else {
                right = middle;
            }
        }
    }

    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[1][0] = 1;
    dp[1][1] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= evenCount[i - 1]; j++) {
            if (dp[i - j][0] + 1 < dp[i + j][0]) {
                dp[i + j][0] = dp[i - j][0] + 1;
                dp[i + j][1] = i - j;
            }

        }

        for (int j = 0; j <= oddCount[i - 1]; j++) {
            if (dp[i - j - 1][0] + 1 < dp[i + j][0]) {
                dp[i + j][0] = dp[i - j - 1][0] + 1;
                dp[i + j][1] = i - j - 1;
            }
        }

    }

    cout << dp[n][0] << "\n";
    rek(n, n);
}