anonymous No title
No License C++
2020年07月02日
Copy
#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    // 二次元配列
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i] == s[j] && i != 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]);
            }
            ans = max(ans, dp[i + 1][j + 1]);
        }
    }

    string ans_string;
    int x = n, y = n;
    while (x > 0 && y > 0) {
        if (dp[x][y] == dp[x - 1][y]) {
            x--;
        } else if (dp[x][y] == dp[x][y - 1]) {
            y--;
        } else {
            x--, y--;
            ans_string = s[x] + ans_string;
        }
    }
    cout << ans_string << '\n';
    cout << ans << '\n';
}

int main() {
    solve();
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    // 二次元配列
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i] == s[j] && i != 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]);
            }
            ans = max(ans, dp[i + 1][j + 1]);
        }
    }

    string ans_string;
    int x = n, y = n;
    while (x > 0 && y > 0) {
        if (dp[x][y] == dp[x - 1][y]) {
            x--;
        } else if (dp[x][y] == dp[x][y - 1]) {
            y--;
        } else {
            x--, y--;
            ans_string = s[x] + ans_string;
        }
    }
    cout << ans_string << '\n';
    cout << ans << '\n';
}

int main() {
    solve();
    return 0;
}

年末年始は機械学習・深層学習を勉強しませんか?
No one still commented. Please first comment.
年末年始は機械学習・深層学習を勉強しませんか?
広告
未経験から最短でエンジニアへの転職を目指すなら