« Longest Palindrome substring

Given a string, find the longest substring which is a palindrome.

Example:

Input: forgeeksskeegfor

Output: geeksskeeg

Input: Geeks

Output: ee

Copy
1#include<iostream>
2#include<iomanip>
3#include<algorithm>
4#include<string>
5#include<cstring>
6#include<vector>
7#include<cmath>
8#include <map>
9#include<climits>
10//climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void printSubString(string str, int start, int end){
15    for(int i=start; i<=end; i++){
16        cout<<str[i];
17    }
18    cout<<endl;
19}
20
21int longestPalindromeSubstring(string str){
22    int n = str.length();
23    vector<vector<bool> > vec(n, vector<bool>(n, false));
24
25    int start = 0;
26    int max = 1;
27
28
29    for(int i = 0; i < n; i++){
30        vec[i][i] = true;
31    }
32
33    for(int i = 0; i < n-1; i++){
34        if(str[i] == str[i + 1]){
35            vec[i][i+1] = true;
36            max = 2;
37            start = i;
38        }
39    }
40
41    for(int k=3; k<n; k++){
42        for(int i=0; i<n-k+1; i++){
43            if(vec[i+1][i+k-2] == true && str[i] == str[i+k-1]){
44                vec[i][i+k-1] = true;
45                if(max < k){
46                    max = k;
47                    start = i;
48                }
49            }
50        }
51    }
52
53    cout << "Longest palindrome substring is: ";
54    printSubString(str, start, start + max - 1);
55
56    return max;
57}
58int main()
59{
60    string str;
61    cin >> str;
62    cout << "Length is: "<< longestPalindromeSubstring(str)<<endl;
63    return 0;
64}