先预处理出从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;
}
最后一次更新于2019-10-27
0 条评论