Manacher 's Algorithm | A C program to implement Manachers Algorithm ; Position count ; LPS Length Array ; centerPosition ; centerRightPosition ; currentRightPosition ; currentLeftPosition ; Uncomment it to print LPS Length array printf ( " % d ▁ % d ▁ " , L [ 0 ] , L [ 1 ] ) ; ; get currentLeftPosition iMirror for currentRightPosition i ; If currentRightPosition i is within centerRightPosition R ; Attempt to expand palindrome centered at currentRightPosition i Here for odd positions , we compare characters and if match then increment LPS Length by ONE If even position , we just increment LPS by ONE without any character comparison ; Track maxLPSLength ; If palindrome centered at currentRightPosition i expand beyond centerRightPosition R , adjust centerPosition C based on expanded palindrome . ; Uncomment it to print LPS Length array printf ( " % d ▁ " , L [ i ] ) ; ; printf ( " \n " ) ;
#include <stdio.h> NEW_LINE #include <string.h> NEW_LINE char text [ 100 ] ; int min ( int a , int b ) { int res = a ; if ( b < a ) res = b ; return res ; } void findLongestPalindromicString ( ) { int N = strlen ( text ) ; if ( N == 0 ) return ; N = 2 * N + 1 ; int L [ N ] ; L [ 0 ] = 0 ; L [ 1 ] = 1 ; int C = 1 ; int R = 2 ; int i = 0 ; int iMirror ; int maxLPSLength = 0 ; int maxLPSCenterPosition = 0 ; int start = -1 ; int end = -1 ; int diff = -1 ; for ( i = 2 ; i < N ; i ++ ) { iMirror = 2 * C - i ; L [ i ] = 0 ; diff = R - i ; if ( diff > 0 ) L [ i ] = min ( L [ iMirror ] , diff ) ; while ( ( ( i + L [ i ] ) < N && ( i - L [ i ] ) > 0 ) && ( ( ( i + L [ i ] + 1 ) % 2 == 0 ) || ( text [ ( i + L [ i ] + 1 ) / 2 ] == text [ ( i - L [ i ] - 1 ) / 2 ] ) ) ) { L [ i ] ++ ; } if ( L [ i ] > maxLPSLength ) { maxLPSLength = L [ i ] ; maxLPSCenterPosition = i ; } if ( i + L [ i ] > R ) { C = i ; R = i + L [ i ] ; } } start = ( maxLPSCenterPosition - maxLPSLength ) / 2 ; end = start + maxLPSLength - 1 ; printf ( " LPS ▁ of ▁ string ▁ is ▁ % s ▁ : ▁ " , text ) ; for ( i = start ; i <= end ; i ++ ) printf ( " % c " , text [ i ] ) ; printf ( " STRNEWLINE " ) ; } int main ( int argc , char * argv [ ] ) { strcpy ( text , " babcbabcbaccba " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " abaaba " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " abababa " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " abcbabcbabcba " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " forgeeksskeegfor " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " caba " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " abacdfgdcaba " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " abacdfgdcabba " ) ; findLongestPalindromicString ( ) ; strcpy ( text , " abacdedcaba " ) ; findLongestPalindromicString ( ) ; return 0 ; }