Shortest Palindromic Substring | C ++ program to find the shortest palindromic substring ; Function return the shortest palindromic substring ; One by one consider every character as center point of even and length palindromes ; Find the longest odd length palindrome with center point as i ; Find the even length palindrome with center points as i - 1 and i . ; Smallest substring which is not empty ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; string ShortestPalindrome ( string s ) { int n = s . length ( ) ; vector < string > v ; for ( int i = 0 ; i < n ; i ++ ) { int l = i ; int r = i ; string ans1 = " " ; string ans2 = " " ; while ( l >= 0 && r < n && s [ l ] == s [ r ] ) { ans1 += s [ l ] ; l -- ; r ++ ; } l = i - 1 ; r = i ; while ( l >= 0 && r < n && s [ l ] == s [ r ] ) { ans2 += s [ l ] ; l -- ; r ++ ; } v . push_back ( ans1 ) ; v . push_back ( ans2 ) ; } string ans = v [ 0 ] ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { if ( v [ i ] != " " ) { ans = min ( ans , v [ i ] ) ; } } return ans ; } int main ( ) { string s = " geeksforgeeks " ; cout << ShortestPalindrome ( s ) ; return 0 ; }