这道题我们先考虑朴素算法:
首先,我们从(s_1)串的第一位开始,枚举(s_2)每一位的对应位置,最后记录最终可以到达的位置,用每一位均如此,模拟即可。
该算法不够好。
考虑优化:我们设(f[i,j])指(s_1[i])打头最少需要多少个字符串才能拼出(2_{j})的(s_2)字符串来。
(f[i,0])暴力预处理。
[f[i,j]=f[i,j-1]+f[(i+f[i,j-1])modulo(s1.size),j-1]
]
最后在二进制拼凑时,不必枚举每一位,因为第一位已经包含所有了。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
const int SIZE = 100 + 5;
string s1, s2;
int n1, n2;
long long f[SIZE][32];
int main()
{
while(cin >> s2 >> n2 >> s1 >> n1)
{
memset(f, 0, sizeof(f));
bool fail = false;
for(int i = 0; i < s1.size(); ++ i)
{
int k = i;
for(int j = 0; j < s2.size(); ++ j)
{
int cnt = 0;
while(s1[k % s1.size()] != s2[j])
{
++ k, ++ cnt;
if(cnt >= s1.size())
{
fail = true;
break;
}
}
k = (k + 1) % s1.size();
++ cnt;
f[i][0] += cnt;
if(fail) break;
}
if(fail) break;
}
if(fail)
{
puts("0");
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];
}
}
long long m = 0, pos = 0;
for(int i = 30; i >= 0; -- i)
{
if(pos + f[pos % s1.size()][i] <= s1.size() * n1)
{
pos += f[pos % s1.size()][i];
m += 1 << i;
}
}
printf("%d
", m / n2);
}
return 0;
}