题目描述

blablabla

样例

blablabla

算法1

(倍增DP) $O(|s1| \times |s2| + log_2(n_1 \times |s_1|))$

预处理 f[i][j] 表示从$s_i$经过多少个字符可以出$2^j$个$s_2$

暴力匹配出 f[i][0], 剩下的用倍增求出

最后就是最多可以经过 $n_1 * |s_1|$ 个字符能出现多少个 $s_2$

时间复杂度

参考文献

C++ 代码

int n1, n2;
ll f[105][20];
char s[105], t[105];

bool check() {
    set<char> st;
    rep (i, 0, n - 1) st.insert(s[i]);
    rep (i, 0, m - 1) if (!st.count(t[i])) return 1;
    return 0;
}

int main() {
    IOS;
    while (cin >> t >> n2 >> s >> n1) {
        n = strlen(s), m = strlen(t); n1 *= n; _ = 0;
        rep (i, 0, n - 1) f[i][0] = 0;
        if (check()) { cout << "0\n"; continue; }
        rep (i, 0, n - 1) rep (j, 0, m - 1) while (s[(++f[i][0] + i - 1) % n] != t[j]);
        rep (i, 1, 19) rep (j, 0, n - 1) 
            f[j][i] = f[j][i - 1] + f[(j + f[j][i - 1]) % n][i - 1];
        for (int i = 19, j = 0; ~i; --i) 
            if (f[j][i] <= n1) _ += 1 << i, n1 -= f[j][i], j = (j + f[j][i++]) % n;
        cout << _ / n2 << '\n';
    }
    return 0;
}