Home PAT 1040 Longest Symmetric String
Post
Cancel

PAT 1040 Longest Symmetric String

Link

dp[i][j] 表示从 s[i]s[j] 的子串是否是回文串, dp[i][j] = 0 或 1.

递推方程:

  • if s[i] == s[j]:
    • dp[i][j] = dp[i+1][j-1]
  • else:
    • dp[i][j] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
string s;
int n,ans=1;
int dp[1010][1010];
int main() {
    getline(cin,s);
    n=s.size();
    for(int i=0;i<n;++i)
        dp[i][i]=1;
    for(int i=1;i<n;++i)
        if(s[i]==s[i-1]){
            dp[i-1][i]=1;
            ans=2;
        }
    for(int len=3;len<=n;++len)
        for(int i=0;i<n-len+1;++i){
            if(s[i]==s[i+len-1])
                dp[i][i+len-1]=dp[i+1][i+len-2];
            if(dp[i][i+len-1]) ans=len;
        }
    printf("%d\n",ans);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.