算法1

推荐： 墨染空的题解 https://www.acwing.com/solution/content/6637/

这里的代码基本是李书的代码

C++ 代码

#include <bits/stdc++.h>
using namespace std;

string s1,s2;
int n1,n2;
long long f[105][32]; //f[i][j]：从i开始，至少需要多少个字符才能拼成2^j个s2

int main(){
    while(cin>>s2>>n2>>s1>>n1){
        int ns1=s1.size(), ns2=s2.size();
        bool yes=true;
        for(int i=0;i<ns1;i++){
            int pos=i;
            f[i][0]=0;
            for(int j=0;j<ns2;j++){
                int cnt=0;
                while(s1[pos] != s2[j]){
                    pos=(pos+1)%ns1;
                    if(++cnt>=ns1) //判断是否无法拼成
                        yes=false, s1[pos]=s2[j], j=ns2, i=ns1; //赋值以便连续跳出
                }
                pos=(pos+1)%ns1;
                f[i][0]+=cnt+1; //+1,==的也要消耗掉
            }
        }
        if(yes==false) {cout<<0<<endl; continue;} //无法拼成，继续下一个
        for(int j=1;j<=30;j++)
            for(int i=0;i<ns1;i++)
                f[i][j]=f[i][j-1]+f[ (i+f[i][j-1])%ns1 ][j-1];
        long long ans=0;
        for(int st=0;st<ns1;st++){ //枚举起点
            if(s1[st]!=s2[0])continue;
            long long x=st, cnt=0;
            for(int k=30;k>=0;k--)
                if(x+f[ x%ns1 ][k] <= ns1*n1){
                    x += f[ x%ns1 ][k];
                    cnt+=1<<k;
                }
            ans=max(ans,cnt);
        }
        cout<<ans/n2<<endl;
    }
}