Submission #74947720

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
// using mint = modint998244353;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

template <typename T> using v = vector<T>;
template <typename T> using vv = vector<vector<T>>;
template <typename T> using vvv = vector<vector<vector<T>>>;

using ll = long long;       using ld = long double;     using vs = v<string>;
using vi = v<int>;          using vll = v<ll>;          using vld = v<ld>;
using vvi = vv<int>;        using vvll = vv<ll>;        using vvld = vv<ld>;
using vvvi = vvv<int>;      using vvvll = vvv<ll>;      using vvvld = vvv<ld>;
using pii = pair<int, int>; using pll = pair<ll, ll>;   using pld = pair<ld, ld>;
using vpii = v<pii>;        using vpll = v<pll>;        using vpld = v<pld>;
using mll = map<ll, ll>;    using umll = unordered_map<ll, ll>;
using pq_gr = priority_queue<ll, vi, greater<ll>>;

// ======================================================================================

/*
    問題 : T * i は S * ? の 部分文字列か？

    T == S * j のとき : inf

    S == Tr + T * j + Tl のとき : inf

    => 問題 : T * i は S * inf の 部分文字列として何連続で出現するか？

    ACL の Z algorithm、
    入力を T + '#' + S + S ( |S| >= |T| ) ってすれば S[i .. i + |T| - 1] == T かどうか取れるのか

    DAG はスニペットにしている
*/

// >---------------- DAG [Begin] ---------------->

struct TopologicalSort {
    int n;
    vvi g;
    vi indeg;

    TopologicalSort(int n) : n(n), g(n), indeg(n) {}

    void add_edge(int a, int b) {
        g[a].push_back(b);
        indeg[b]++;
    }

    // false のとき閉路あり
    // true のとき、order がトポロジカルソート順
    bool sort(vi &order) {
        // 辞書順最小にしたいなら
        // priority_queue<int, vi, greater<int>> q;
        queue<int> q;
        vi deg = indeg;

        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) q.push(i);
        }

        while (!q.empty()) {
            int v = q.front(); q.pop();
            order.push_back(v);

            for (int to : g[v]) {
                deg[to]--;
                if (deg[to] == 0) q.push(to);
            }
        }

        return (int)order.size() == n;
    }
};

// DAG 上の最長パスと親の記録
// dp[t] = 任意始点から t までの最長距離
// usage : auto [dp, par] = longest_path_dag(ts.g, order);
pair<vi, vi> longest_path_dag(const vvi &g, const vi &order) {
    int n = g.size();
    vi dp(n), par(n, -1);

    for (int v : order) {
        for (int to : g[v]) {
            if (dp[to] < dp[v] + 1) {
                dp[to] = dp[v] + 1;
                par[to] = v;
            }
        }
    }

    return {dp, par};
}

// t までの経路復元
vi restore_path(int t, const vi &par) {
    vi path;
    while (t != -1) {
        path.push_back(t);
        t = par[t];
    }
    reverse(path.begin(), path.end());
    return path;
}

// <---------------- DAG [ End ] ----------------<

void solve() {
    string S, T;
    cin >> S >> T;
    string s = S;
    while (S.size() < T.size()) S += s;

    int N = S.size(), M = T.size();

    string C = T + '#' + S + S;
    vi za = z_algorithm(C);

    TopologicalSort ts(N);
    int fix = M + 1;
    for (int i = 0; i < N; i++) {
        if (za[i + fix] == M) {
            ts.add_edge(i, (i + M) % N);
        }
    }

    vi order;
    if (!ts.sort(order)) {
        cout << -1 << '\n';
        return;
    }

    auto [dp, _] = longest_path_dag(ts.g, order);
    cout << *max_element(all(dp)) << '\n';
}

// ======================================================================================

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int T; cin >> T;
    // while (T--) solve();

    solve();
}

Submission Info

Judge Result