답안 #874320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874320 2023-11-16T16:33:49 Z RedGrey1993 원형 문자열 (IZhO13_rowords) C++17
100 / 100
76 ms 22124 KB
#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, const pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
template <unsigned int MOD>
class ModInt {
public:
    ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
    explicit operator bool() const { return val != 0; }
    ModInt operator-() const { return ModInt() - *this; }
    ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
    ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
    ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
    ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
    ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
    ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
    ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
    ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
    // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
    unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
    bool operator==(const ModInt &r) const { return val == r.val; }
    bool operator!=(const ModInt &r) const { return val != r.val; }
    ModInt pow(long long n) const {
        ModInt x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv() const { return pow(MOD - 2); }
    unsigned int get_val() { return val; }
    friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
    friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
    unsigned int val;
    ModInt &set_v(unsigned int _v) {
        val = (_v < MOD) ? _v : _v - MOD;
        return *this;
    }
};
constexpr unsigned int mod = 1e9+7;
using Mint = ModInt<mod>;
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif
 
using Mint2 = ModInt<mod-1>;
class Solution {
    struct Line {
        long long m, c;
        long long Eval(long long x) { return m * x + c; }
        long double IntersectX(Line l) { return (long double)(c - l.c) / (l.m - m); }
    };

public:
    void Solve() {
        string s,t;
        while(cin>>s>>t) {
            s += s;
            // dbg(s);
            int n = sz(s), m=sz(t);

            auto clcs = [&] () {
                vector<vi> dp(n+1, vi(m+1));
                vector<vi> parent(n+1, vi(m+1));
                rep(i,1,n+1) parent[i][0] = 2;

                rep(i,0,n) {
                    rep(j,0,m) {
                        if (s[i] == t[j]) dp[i+1][j+1] = dp[i][j] + 1;
                        else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);

                        if (dp[i+1][j+1] == dp[i+1][j]) parent[i+1][j+1] = 0;
                        else if (s[i] == t[j] && dp[i+1][j+1] == dp[i][j] + 1) parent[i+1][j+1] = 1;
                        else parent[i+1][j+1] = 2;
                    }
                }

                auto lcs = [&] (int root) {
                    int x = root + n/2;
                    int y = m;
                    int cnt = 0;
                    while (x > root && y > 0) {
                        if (parent[x][y] == 1) {
                            cnt++;
                            x--; y--;
                            // dbg(mp(x,y));
                            // dbg(cnt);
                        } else if (parent[x][y] == 0) y--;
                        else x--;
                    }
                    return cnt;
                };

                auto reroot = [&] (int root) {
                    int x = root;
                    int y = 0;

                    while (y <= m && parent[x][y] != 1) y++;
                    if (y > m) return;

                    parent[x][y] = 0;
                    while (x < n && y < m) {
                        if (parent[x+1][y] == 2) {
                            x++;
                            parent[x][y] = 0;
                        } else if (parent[x+1][y+1] == 1) {
                            x++; y++;
                            parent[x][y] = 0;
                        } else {
                            y++;
                        }
                    }

                    while (x < n && parent[x+1][y] == 2) {
                        x++;
                        parent[x][y] = 0;
                    }
                };

                int ans = 0;
                ans = max(ans, lcs(0));
                rep(root, 1, n/2) {
                    reroot(root);
                    ans = max(ans, lcs(root));
                }
                // dbg(ans);
                return ans;
            };

            int ans = clcs();
            reverse(all(s));
            ans = max(ans, clcs());
            cout << ans << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
#if USACO
    set_io("time");
#else
    set_io("input");
#endif
    Solution().Solve();

    return 0;
}


# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 6 ms 2136 KB Output is correct
7 Correct 27 ms 16280 KB Output is correct
8 Correct 57 ms 16264 KB Output is correct
9 Correct 69 ms 16168 KB Output is correct
10 Correct 52 ms 16264 KB Output is correct
11 Correct 53 ms 17752 KB Output is correct
12 Correct 37 ms 20616 KB Output is correct
13 Correct 74 ms 20616 KB Output is correct
14 Correct 70 ms 18624 KB Output is correct
15 Correct 71 ms 22124 KB Output is correct
16 Correct 69 ms 17856 KB Output is correct
17 Correct 47 ms 13684 KB Output is correct
18 Correct 76 ms 21104 KB Output is correct
19 Correct 53 ms 16484 KB Output is correct
20 Correct 72 ms 19036 KB Output is correct
21 Correct 20 ms 4700 KB Output is correct
22 Correct 31 ms 7768 KB Output is correct
23 Correct 43 ms 10744 KB Output is correct
24 Correct 53 ms 11232 KB Output is correct
25 Correct 56 ms 14936 KB Output is correct