#include<bits/stdc++.h>

using namespace std;

int P[200001]; // Longest Palidrome centered around position i
int S[200001]; // Longest Palidrome that starts at position i "lower bound of the radius"
int E[200001]; // Longest Palidrome that ends   at position i "upper bound of the radius"
int Pr[200001];
int N;
int n;
string s;

void manacher()
{
    N = 2*n + 1;
    P[0] = 0;
    E[0] = 0;

    int center = 0;
    int centerRight = 0;
    int i;

    int maxLPSLength = 0;
    int maxLPSCenterPosition = 0;

    int distToEdge;

    for (i = 1; i < N; i++)
    {
        P[i] = 0;
        distToEdge = centerRight - i;
        if(distToEdge > 0) {
            P[i] = min(P[center*2-i], distToEdge);
            if(i-P[i] <= N/2)
                S[ i-P[i] ] = max(S[ i-P[i] ], P[i]);
            if(i+P[i] >=  N/2)
                E[ i+P[i] ] = max(E[ i+P[i] ], P[i]);
        }

        while
        (
        	(i + P[i] < N - 1) && (i - P[i] > 0) &&
			(
				( (i + P[i])&1 ) ||
				( s[(i+P[i])/2]==s[(i-P[i]-1)/2] )
			)
		)
        {
        	P[i]++;
        	if(i-P[i] <= N/2)
                S[ i-P[i] ] = max(S[ i-P[i] ], P[i]);
            if(i+P[i] >=  N/2)
                E[ i+P[i] ] = max(E[ i+P[i] ], P[i]);
        }

		if(P[i] > maxLPSLength) {
			maxLPSLength = P[i];
			maxLPSCenterPosition = i;
		}

        if (i + P[i] > centerRight) {
        	center = i;
            centerRight = i + P[i];
        }
    }

    Pr[N-1] = 0;
    S[N-1] = 0;

    center = N-1;
    int centerLeft = N-1;

    for (i = N-2; i >= 0; i--)
    {
        Pr[i] = 0;
        distToEdge = i - centerLeft;
        if(distToEdge > 0) {
            Pr[i] = min(Pr[center*2-i], distToEdge);
            if(i-Pr[i] > N/2)
                S[ i-Pr[i] ] = max(S[ i-Pr[i] ], Pr[i]);
            if(i+Pr[i] <  N/2)
                E[ i+Pr[i] ] = max(E[ i+Pr[i] ], Pr[i]);
        }

        while
        (
        	(i - Pr[i] > 0) && (i + Pr[i] < N - 1) &&
			(
				( (i - Pr[i])&1 ) ||
				( s[(i-Pr[i]-1)/2]==s[(i+Pr[i])/2] )
			)
		)
        {
            Pr[i]++;
            if(i-Pr[i] > N/2)
                S[ i-Pr[i] ] = max(S[ i-Pr[i] ], Pr[i]);
            if(i+Pr[i] <  N/2)
                E[ i+Pr[i] ] = max(E[ i+Pr[i] ], Pr[i]);
        }

        if (i - Pr[i] > centerLeft) {
        	center = i;
            centerLeft = i + Pr[i];
        }
    }

    int start = (maxLPSCenterPosition - maxLPSLength)/2;
    cout << "String:  " << s << '\n';
    cout << "MString: #"; for(int i = 0; i < s.length(); i++) cout << s[i] << '#'; cout << '\n';
    cout << "The Longest Palindromic Substring: " << s.substr(start, maxLPSLength) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    s = "cbcbaaabc";
    n = s.length();
    manacher();

    cout << "The Longest Palindrome Length Starting at Every Index:\n";
    for(int i = 0; i < n; i++)
        cout << max(S[i*2], S[i*2+1]) << ' ';
    cout << '\n';
    cout << "The Longest Palindrome Length Ending at Every Index:\n";
    for(int i = 0; i < n; i++)
        cout << max(E[i*2+1], E[i*2+2]) << ' ';
    cout << "\n\n";

    memset(P, 0, sizeof(P));
    memset(Pr, 0, sizeof(Pr));
    memset(S, 0, sizeof(S));
    memset(E, 0, sizeof(E));
    s = "cbcbbcc";
    n = s.length();
    manacher();

    cout << "The Longest Palindrome Length Starting at Every Index:\n";
    for(int i = 0; i < n; i++)
        cout << max(S[i*2], S[i*2+1]) << ' ';
    cout << '\n';
    cout << "The Longest Palindrome Length Ending at Every Index:\n";
    for(int i = 0; i < n; i++)
        cout << max(E[i*2+1], E[i*2+2]) << ' ';
    cout << "\n\n";

    memset(P, 0, sizeof(P));
    memset(Pr, 0, sizeof(Pr));
    memset(S, 0, sizeof(S));
    memset(E, 0, sizeof(E));
    s = "dcbcbbcccbbcbc";
    n = s.length();
    manacher();

    cout << "The Longest Palindrome Length Starting at Every Index:\n";
    for(int i = 0; i < n; i++)
        cout << max(S[i*2], S[i*2+1]) << ' ';
    cout << '\n';
    cout << "The Longest Palindrome Length Ending at Every Index:\n";
    for(int i = 0; i < n; i++)
        cout << max(E[i*2+1], E[i*2+2]) << ' ';
    cout << "\n\n";

    return 0;
}