#include <bits/stdc++.h>

using namespace std;

ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
vector<int> p;
string s;
string s2; ///stringul prelucrat a#b#c#d#...f#
void manacher(string s){
    int n=s2.length();
    p.assign(n,1);
    int l=1, r=1;
    for(int i=1; i<n; ++i){
        p[i]=max(1,min(r-i, p[l+r-i])); ///
        while(i+p[i]<n && i-p[i]>=0 && s2[i+p[i]]==s2[i-p[i]]){
            p[i]++; ///expanding
        }
        if(i+p[i]>r){
            l=i-p[i];
            r=i+p[i];
        }
    }

}
int main()
{
    fin >> s;
    for(auto i : s){
        s2+=string("#")+i;
    }
    s2+="#";
    cout << s2 << '\n';
    manacher(s2);
    for(auto i: p){
        cout << i << ' ';
    }
    int ans=0;
    for(auto i : p){
        ans+=i/2;
    }
    fout << ans;
    return 0;
}