Minimum insertions to form shortest palindrome | C ++ program to find minimum number of insertions on left side to form a palindrome . ; Returns true if a string str [ st . . end ] is palindrome ; Returns count of insertions on left side to make str [ ] a palindrome ; Find the largest prefix of given string that is palindrome . ; Characters after the palindromic prefix must be added at the beginning also to make the complete string palindrome ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPalin ( char str [ ] , int st , int end ) { while ( st < end ) { if ( str [ st ] != str [ end ] ) return false ; st ++ ; end -- ; } return true ; } int findMinInsert ( char str [ ] , int n ) { for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( isPalin ( str , 0 , i ) ) return ( n - i - 1 ) ; } } int main ( ) { char Input [ ] = " JAVA " ; printf ( " % d " , findMinInsert ( Input , strlen ( Input ) ) ) ; return 0 ; }