PALIN - Xâu con đối xứng dài nhất

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Xâu ký tự ~X~ được gọi là xâu con của xâu ký tự ~Y~ nếu ta có thể xoá đi một số ký tự trong xâu ~Y~ để được xâu ~X~.

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

Bài toán:

Một xâu ký tự ~S~ (chỉ gồm các ký tự chữ cái latin) hãy tìm một xâu con đối xứng dài nhất của xâu ~S~.

Input

  • Một dòng duy nhất chứa xâu ~S~.

Giới hạn:

  • Độ dài xâu ~S~ không quá ~2000~ ký tự.

Output

  • Mộ dòng duy nhất ghi độ dài sâu con dài nhất tìm được.

Sample

Input #1
lmevxeyzl
Output #1
5

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -3
    top1sever  đã bình luận lúc 1, Tháng 3, 2024, 16:06

    include <bits/stdc++.h>

    define MINH int main

    define st string

    define FASTER iosbase::syncwith_stdio(false);cin.tie(NULL);

    typedef long long ll; const int maxn=5000; using namespace std; string x,y; int n,m,f[maxn][maxn]; //================================================ //================================================ MINH() { FASTER; freopen("1.inp","r",stdin); freopen("1.out","w",stdout); cin>>x; n=x.size(); y=x; reverse(y.begin(),y.end()); x='@'+x;y='@'+y; m=n; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(x[i]==y[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } cout<<f[n][m]; return 0; } //𝕦𝕞𝕙𝕝^^ //█▀▀ █▀█ █▀▄ █▀▀   █▄▄ █▄█   █▀▄▀█ █ █▄░█ █░█ //█▄▄ █▄█ █▄▀ ██▄   █▄█ ░█░   █░▀░█ █ █░▀█ █▀█


  • 3
    dungolduck  đã bình luận lúc 14, Tháng 2, 2024, 7:25

    các bạn tham khảo: nó lấy ý tưởng tương tự như bài sâu đối xứng liên tiếp với bài này không liên tiếp bạn chỉ cần check trong cái đoạn đó có sâu đối xứng thì sẽ cộng thêm 2 vào là đc còn trường hợp 2 kí tự liên tiếp sẽ phân riêng ra như code của mình:

    string s;
cin >> s;
int n=s.length();
int a[n][n];
for(int i=0;i&lt;n;i++){
    for(int j=0;j&lt;n;j++){
        if(i==j) a[i][j]=1;
        else a[i][j]=0;
    }
}



for(int k=2;k<=n;k++){
    for(int i=0;i&lt;n-k+1;i++){
        int j=i+k-1;
        a[i][j]= max(a[i+1][j], a[i][j-1]);
        if(s[i]==s[j]){
            if(k==2)    a[i][j]=2;
            else{
                a[i][j]= a[i+1][j-1]+2;
            }
        }
    }
}
cout << a[0][n-1];
return 0;

    }