计算重复

AcWing-294-计算重复

分析

见《进阶指南》第309页。

实现

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 110, M = 32;
int n1, n2;
string s1, s2;
LL f[N][M];

int main () {
    while (cin >> s2 >> n2 >> s1 >> n1) {
        memset(f, 0, sizeof(f));
        int l1 = s1.size(), l2 = s2.size();
        bool flag = true;
        for (int i = 0; i < l1; ++ i) {
            int ptr = i;
            for (int j = 0; j < l2; ++ j) {
                int cnt = 0;
                while (s1[ptr] != s2[j]) {
                    ptr = (ptr + 1) % l1;
                    ++ cnt;
                    if (cnt >= l1) {
                        flag = false;
                        break;
                    }
                }
                if (flag == false) break;
                ptr = (ptr + 1) % l1;
                f[i][0] += cnt + 1;
            }
            if (flag == false) break;
        }
        if (flag == false) {
            cout << 0 << endl;
            continue;
        }
        // 预处理
        for (int j = 1; j <= 30; ++ j)
            for (int i = 0; i < l1; ++ i)
                f[i][j] = f[i][j - 1] + f[(i + f[i][j - 1]) % l1][j - 1];
        // 拼凑
        LL res = 0;
        for (int i = 0; i < l1; ++ i) {
            LL ptr = i, len = 0;
            for (int k = 30; k >= 0; -- k) {
                if (ptr + f[ptr % l1][k] <= l1 * n1) {
                    ptr += f[ptr % l1][k];
                    len += 1 << k;
                }
            }
            res = max(res, len);
        }
        cout << res / n2 << endl;
    }
    return 0;
}