#include<bits/stdc++.h> using namespace std; int k; string s,t,S; int n,m,len; int sa[100005],rk[200005],lst[200005],ht[200005],st[17][200005],lg[200005]; void SA(){ // cout<<s<<endl<<t<<endl<<S<<endl; for(int i=1;i<=len;i++)sa[i]=i,rk[i]=S[i]; for(int w=1;w<len;w<<=1){ sort(sa+1,sa+1+len,[&](int x,int y){return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];}); memcpy(lst,rk,sizeof(rk)); for(int i=1,p=0;i<=len;i++){ if(lst[sa[i]]==lst[sa[i-1]]&&lst[sa[i]+w]==lst[sa[i-1]+w])rk[sa[i]]=p; else rk[sa[i]]=++p; } } // for(int i=1;i<=len;i++)cout<<sa[i]<<" "<<rk[i]<<endl; for(int i=1,k=0;i<=len;i++){ if(!rk[i])continue; if(k)k--; while(S[i+k]==S[sa[rk[i]-1]+k]){ // cout<<i+k<<" "<<sa[rk[i]-1]+k<<" "<<s[i+k]<<" "<<s[sa[rk[i]-1]+k]<<endl; k++; } ht[rk[i]]=st[0][rk[i]]=k; // cout<<k<<endl; } // for(int i=1;i<=len;i++)cout<<ht[i]<<endl; for(int i=1;i<=16;i++)for(int j=1;j+(1<<i)-1<=len;j++)st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]); } int lcp(int x,int y){ if(x>n||y>m)return 0; x=rk[x],y=rk[y+n+1]; if(x>y)swap(x,y); x++; // cout<<x<<" "<<y<<" "<<min(st[lg[y-x+1]][x],st[lg[y-x+1]][y-(1<<lg[y-x+1])+1])<<endl; return min(st[lg[y-x+1]][x],st[lg[y-x+1]][y-(1<<lg[y-x+1])+1]); } int dp[100][100],ans[100],f[100005]; void mn(int &x,int y){if(x>y)x=y;} void mx(int &x,int y){if(x<y)x=y;} void slv(){ cin>>k>>s>>t; n=s.size(),m=t.size(); s=' '+s,t='#'+t; S=s+t; len=S.size()-1; for(int i=2;i<=len;i++)lg[i]=lg[i>>1]+1; SA(); // for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cout<<i<<" "<<j<<" "<<lcp(i,j)<<endl; for(int i=1;i<=m;i++){ memset(dp,0xff,sizeof dp); dp[0][k]=lcp(1,i); for(int j=0;j<k;j++)for(int x=-j;x<=j;x++)if(dp[j][x+k]>=0){ int a=dp[j][x+k],b=a+x+i-1; if(a<n)mx(dp[j+1][x+k-1],a+1+lcp(a+2,b+1)); if(b<m)mx(dp[j+1][x+k+1],a+lcp(a+1,b+2)); if(a<n&&b<m)mx(dp[j+1][x+k],a+1+lcp(a+2,b+2)); } // for(int j=0;j<k;j++){ // for(int x=-j;x<=j;x++){ // cout<<dp[j][x+k]<<" "; // } // cout<<endl; // } int l=max(i,i-1+n-k-k),r=min(m,i-1+n+k+k); for(int j=l;j<=r;j++)f[j]=k+1; for(int j=0;j<=k;j++)for(int x=-k;x<=k;x++)if(dp[j][x+k]>=n){ mn(f[i-1+n+x],j); } for(int j=l;j<r;j++)mn(f[j+1],f[j]+1); for(int j=r;j>l;j--)mn(f[j-1],f[j]+1); for(int j=l;j<=r;j++)ans[f[j]]++; } for(int i=0;i<=k;i++)cout<<ans[i]<<endl; } int main(){ // int T;cin>>T;while(T--) slv(); return 0; }