#include<bits/stdc++.h> #define int long long using namespace std; const int B=31; const int mod=1011451423; const int N=1e5+7; const int K=37; int n,m,k; char S[N],T[N]; int Pow[N],H[N][2]; inline void CMax(int &a,int b){a=max(a,b);} inline void Init(){ cin>>k; cin>>S+1>>T+1; n=strlen(S+1),m=strlen(T+1); Pow[0]=1; for(int i=1;i<=max(n,m);i++)Pow[i]=Pow[i-1]*B%mod; for(int i=1;i<=n;i++)H[i][0]=(H[i-1][0]*B%mod+S[i]-'A')%mod; for(int i=1;i<=m;i++)H[i][1]=(H[i-1][1]*B%mod+T[i]-'A')%mod; } inline int Has(int l,int r,int t){ return (H[r][t]-H[l-1][t]*Pow[r-l+1]%mod+mod)%mod; } inline bool Eq(int P1,int P2,int Len){ if(!Len)return 1; return Has(P1,P1+Len-1,0)==Has(P2,P2+Len-1,1); } inline int LCP(int P1,int P2){ int l=0,r=min(n-P1+1,m-P2+1); while(l<r){ int mid=l+r+1>>1; if(Eq(P1,P2,mid))l=mid; else r=mid-1; }return l; } int f[K][K<<1]; int Ans[K]; inline void DP(int L){ memset(f,-63,sizeof(f)); f[0][k]=0; for(int i=0;i<=k;i++){ for(int j=0;j<=(k<<1);j++){ if(f[i][j]>=0&&f[i][j]+j-k>=0&&L-1+f[i][j]+j-k<=m){ // 状态可达到 && 匹配的 S 合法 && 匹配的 T(加上前面的 L)不超过 m f[i][j]+=LCP(f[i][j]+1,L+f[i][j]+j-k); CMax(f[i+1][j+1],f[i][j]);/*Ins*/ if(j)CMax(f[i+1][j-1],f[i][j]+(f[i][j]!=n));/*Del*/ CMax(f[i+1][j],f[i][j]+(f[i][j]!=n));/*Replace*/ } } } for(int j=0;j<=2*k;j++){ for(int i=0;i<=k;i++){ if(f[i][j]==n&&n+j-k>0&&L-1+n+j-k<=m){ // 状态能够匹配 S 全串 && S 此时对应的 T 非空 && 匹配的 T(加上前面的 L)不超过 m Ans[i]++; break; //[L,L-1+n+j-k] } } } } signed main(){ #ifndef ONLINE_JUDGE freopen("edit.in","r",stdin); freopen("edit.out","w",stdout); #endif Init(); for(int i=1;i<=m;i++)DP(i); for(int i=0;i<=k;i++)cout<<Ans[i]<<endl; cout<<endl; return 0; }