先预处理出从s1的第i个字符为开头,至少需要多少个字符才能生成$s2$。
之后套路处理出s2的$2^i$次方需要的字符数量,由于可能很大,但$s1$存在循环,膜一下就好了。
最后枚举从第$i$个字符为开头,拼凑出的最多次方。
之后答案除以n2。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int N=105;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar(x%10+48);
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
char s1[N],s2[N];
ll f[N][32];
int main()
{
    while(scanf("%s",s2)!=EOF)
    {
        int n2,n1;
        qr(n2);scanf("%s",s1);qr(n1);
        int l2=strlen(s2),l1=strlen(s1);
        bool bk=0;
        for(int i=0;i<l1;i++)
        {
            int pos=i;f[i][0]=0;
            for(int j=0;j<l2;j++)
            {
                int cnt=0;
                while(s1[pos]!=s2[j])
                {
                    pos=(pos+1)%l1;
                    if(++cnt>=l1){puts("0");bk=1;break;}
                }
                if(bk)break;
                pos=(pos+1)%l1;
                f[i][0]+=cnt+1;
            }
            if(bk)break;
        }
        if(bk)continue;
        for(int j=1;j<=30;j++)
            for(int i=0;i<l1;i++)//f[i][j]表示从s1[i]开始,至少需要多少个字符才能生成conn(s2,2^j) 
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%l1][j-1];//从s1[i]开始,从i+f[i][j-1]开始,由于存在循环l1,所以从(i+f[i][j-1])%l1开始
        ll m=0;
        for(int st=0;st<l1;st++)
        {
            ll ans=0,x=st;
            for(int k=30;~k;k--)
                if(x+f[x%l1][k]<=1ll*l1*n1)
                {
                    x+=f[x%l1][k];
                    ans+=1<<k;
                }
            m=max(ans,m);
        }   
        qw(m/n2);puts("");
    }
    return 0;
}