设 F[i,j]表示从 s1[i] 开始，至少需要多少个字符，才能生成 conn(s2,2j)。
F[i,j]=F[i,j−1]+F[(i+F[i,j−1])mod∣s 1∣,j−1]
做倍增优化DP，首先是预处理出若干与2的整数次幂相关的代表状态，再拼凑出答案。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
string s1,s2;
int n1,n2;
ll f[110][32];
int main()
{
    //freopen("in.txt","r",stdin);
    while(cin>>s2>>n2>>s1>>n1)
    {
        bool flag=false;
        memset(f,0,sizeof(f));
        for(int i=0;i<s1.size();i++)
        {
            int pos=i;f[i][0]=0;
            for(int j=0;j<s2.size();j++)
            {
                int cnt=0;
                while(s1[pos]!=s2[j])
                {
                    pos=(pos+1)%s1.size();
                    if(++cnt>=s1.size())
                    {
                        cout<<0<<endl;
                        flag=true;
                    }
                    if(flag)break;
                }
                if(flag)break;
                pos=(pos+1)%s1.size();
                f[i][0]+=cnt+1;
            }
            if(flag)break;
        }
        if(flag)continue;
        for(int j=1;j<=30;j++)
            for(int i=0;i<s1.size();i++)
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%s1.size()][j-1];
        ll m=0;
        for(int i=0;i<s1.size();i++)
        {
            ll x=i,ans=0;
            for(int k=30;k>=0;k--)
                if(x+f[x%s1.size()][k]<=s1.size()*n1)
                {
                    ans+=1<<k;
                    x+=f[x%s1.size()][k];
                }
            m=max(m,ans);
        }
        cout<<m/n2<<endl;
    }
    return 0;
}