Advertisement
Shuva_Dev

Maximum length of palindrome substring | O(n^2) solution for odd length substring

Nov 20th, 2022 (edited)
799
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Time Complexity: O(n^2)
  5. // For ODD Length String
  6. int main() {
  7.     int L, R;
  8.     string s;
  9.     cin >> s;
  10.     int max_len = 0;
  11.     for(int center = 0; center < s.size(); center++) {
  12.         int cur_len = 1;
  13.         for(int k=1; center-k >= 0 && center+k <=s.size(); k++) {
  14.             if(s[center-k] != s[center+k]) break;
  15.             else {
  16.                 cur_len += 2;
  17.             }
  18.         }
  19.         if(cur_len > max_len) {
  20.             max_len = cur_len;
  21.             L = center - cur_len/2;
  22.             R = center + cur_len/2;
  23.         }
  24.  
  25.     }
  26.     cout << max_len << endl;
  27.     for(int i=L;i<=R;i++) {
  28.         cout << s[i];
  29.     }
  30.  
  31.     return 0;
  32. }
  33.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement