PalPal

#include <bits/stdc++.h>
#define N 100001
using namespace std;
char s[N];
int k,l,i,nr,L,sol[N],aux[N];
bool F[N],F1[N];

void solve(int start)
{
    int sz=0;
    nr=0;
    for(i=0;i+start+1<L;++i)
        if(s[i]==s[i+start+1])
            F[i]=0,++nr,aux[sz]=i,++sz;
    sol[start+2]=nr;
    for(l=start+2;l+2<=k;l+=2)
    {
        nr=0;
        int sz2=sz;
        sz=0;
        for(int poz=0;poz<sz2;++poz)
        {
            i=aux[poz];
            if(i==0)
            continue;
            if(i+l>=L)
                break;
            if(s[i-1]==s[i+l])
                ++nr,aux[sz]=i-1,++sz;
        }
        sol[l+2]=nr;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ifstream f("palpal.in");
    f>>s>>k;
    f.close();
    L=strlen(s);
    solve(1);
    solve(0);
    sol[1]=L;
    ofstream g("palpal.out");
    for(i=1;i<=k;++i)
        g<<sol[i]<<'\n';
    g.close();
    return 0;
}