Chuỗi đối xứng

Points: 0.06 (partial)

Time limit: 1.0s

Memory limit: 512M

Input: stdin

Output: stdout

Problem source:

VNOI Marathon '08 - Practice RoundProblem Setter: Ngô Minh Ðức

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi ~s~ cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.

Input

Gồm một dòng duy nhất chứa chuỗi ~s~, chỉ gồm những chữ cái in thường. Chuỗi ~s~ có độ dài không vượt quá ~2000~.

Output

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu ~s~. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Sample Input

lmevxeyzl

Sample Output

level

Comments

Please read the guidelines before commenting.

-5

kietjumper commented on Nov. 10, 2024, 4:16 p.m.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef unsigned long long ull;

#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define EL printf("\n")
#define sz(A) (int) A.size()
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 2500;
int n, F[N][N];
string s, ans;

void solve(int i, int j, int L, int R) {
    if (L > R) return ;
    if (i == j) ans[L] = s[i];
    else {
        if (s[i] == s[j]) {
            ans[L] = ans[R] = s[i];
            solve(i+1, j-1, L+1, R-1);
        } else {
            if (F[i][j] == F[i+1][j])
                solve(i+1, j, L, R);
            else
                solve(i, j-1, L, R);
        }
    }
}

int main() {
//  freopen("INP.TXT", "r", stdin);
//  freopen("OUT.TXT", "w", stdout);


    getline(cin, s);
    n = s.size()-1;
    FOD(i,n,0)
    FOR(j,i,n) {
        if (i == j) F[i][j] = 1;
        else {
            if (s[i] == s[j]) {
                if (i == j-1)
                    F[i][j] = 2;
                else
                    F[i][j] = F[i+1][j-1] + 2;
            } else
                F[i][j] = max(F[i+1][j], F[i][j-1]);
        }
    }

    ans.resize(F[0][n]);

    solve(0, n, 0, F[0][n]-1);

    cout << ans;

    return 0;
}

This comment is hidden due to too much negative feedback. Show it anyway.

3

huydepchai152 commented on Oct. 15, 2023, 2:55 a.m.

test bài này hơi yếu

-1

PaDi commented on Oct. 14, 2023, 4:36 p.m.

hay them test "vmovvov"

20

hieuhfgr commented on June 27, 2022, 12:26 p.m.

cho mình thắc mắc là trong pascal hình như không có kiểu dữ liệu nào chứa đến 2000 kí tự thì phải thì sao làm bài này được nhỉ?

80

darkkcyan commented on June 27, 2022, 12:30 p.m.

Chào bạn.

Nếu bạn nói đến kiểu dữ liệu string trong Turbo Pascal hay Freepascal thì đúng là kiểu dữ liệu này chứa tối đa ~255~ kí tự.

Tuy nhiên trong Freepascal có kiểu dữ liệu ansistring có thể chứa không giới hạn kí tự. Bạn chỉ cần thay string bằng ansistring và dùng kiểu dữ liệu này như kiểu string bình thường.

Ngoài ra bạn cũng có thể thêm dòng lệnh {$H+} lên đầu chương trình, vậy mọi biến có kiểu dữ liệu string sẽ được trình dịch thay thế bằng ansistring luôn và bạn không phải làm gì thêm.

Bạn có thể tham khảo thêm tại https://wiki.freepascal.org/Ansistring và https://www.freepascal.org/docs-html/prog/progsu25.html