| 2 | using namespace std; |
| 3 | |
| 4 | void solve(string s){ |
| 5 | int n = s.size(); |
| 6 | bool dp[n+1][n+1]; |
| 7 | memset(dp,false,sizeof(dp)); |
| 8 | |
| 9 | //single character count |
| 10 | for(int i=0;i<n;i++){ |
| 11 | dp[i][i] = true; |
| 12 | } |
| 13 | |
| 14 | //2 character length count |
| 15 | for(int i=0;i<n-1;i++){ |
| 16 | if(s[i] == s[i+1]){ |
| 17 | dp[i][i+1] = true; |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | //more than 2 character length |
| 22 | |
| 23 | for(int k=2;k<n;k++){ |
| 24 | int i = 0, j = k; |
| 25 | |
| 26 | while(j<n){ |
| 27 | |
| 28 | if(s[i] == s[j] && dp[i+1][j-1]){ |
| 29 | dp[i][j] = true; |
| 30 | }else{ |
| 31 | dp[i][j] = false; |
| 32 | } |
| 33 | |
| 34 | i++; j++; |
| 35 | } |
| 36 | } |
| 37 | |
| 38 | string ans; |
| 39 | int s_l = 0; |
| 40 | for(int i=0;i<n;i++){ |
| 41 | for(int j=n-1;j>=0;j--){ |
| 42 | if(dp[i][j]){ |
| 43 | string s2 = s.substr(i,j-i+1); |
| 44 | if(s2.size() > s_l){ |
| 45 | ans = s2; |
| 46 | s_l = s2.size(); |
| 47 | } |
| 48 | } |
| 49 | } |
| 50 | } |
| 51 | |
| 52 | cout << ans << endl; |
| 53 | |
| 54 | } |
| 55 | |
| 56 | int main() { |
| 57 | //code |