Manacher's algorithm is used to find longest palindrome substring in a string. The worst case time complexity of this algorithm is O(n) and space complexity is also O(n) where n is the length of input string. Note that extend() and mirror() need not to be separate methods and could be done in single pass, but I have separated them on purpose to …

ManachersAlgorithm.cpp

//  Mancher.cpp
//
//  Created by Anirvana Mishra on 6/30/13.
//  Copyright (c) 2013 Anirvana Mishra. All rights reserved.
//  Code is inspired by the algorithm explained here: http://wcipeg.com/wiki/index.php?title=Longest_palindromic_substring

#include <iostream>
#include <vector>
using namespace std;

int extend(char *str,int left, int right,int len){ //Extend the window on both sides to find the longest palindrome centered at current index
    
    int count=0;
    
    while((left>-1) && (right<len) && (str[left]==str[right])){
        left--;
        right++;
        count++;
    }
    
    return count;
}

int mirror(vector<int> &lengths, int i){ //Mirror the longest palindrome lengths from left to right
    
    int delta=lengths[i];
    for(int j=1;j<=delta;j++){
        if(i-delta<j-lengths[j]) lengths[i+j]=lengths[i-j]; //uninteresting index
        else return i+j; //If the starting index of current longest palidrome is right of the starting index of this index, that makes it an interesting index
    }
    return i+delta+1; //next interesting index
}

char * normalize(char *str, int &len){ //Make length odd
    char *newstr=new char[len*2];
    int j=0;
    for(int i=0;i<len-1;i++){
        newstr[j++]=str[i];
        newstr[j++]='$';
    }
    newstr[j++]=str[len-1];
    newstr[j]='\0';
    len=2*len;
    return newstr;
}

pair<int, int> longestPalindrome(char *str){ //Return start and end index pair for the longest common palindrome
    int len=(int)strlen(str);
    pair<int, int> palindrome;
    str=normalize(str,len); //Insert sentinels to make length odd
    vector<int> lengths(len+1,0);
    int index=0;
    
    for(int i=1;i<len;){
        lengths[i]=extend(str, i-1, i+1, len); //Find the longest palindrome starting at this index
        i=mirror(lengths, i); //Mirror indices from left to right and get the next interesting index
    }
    
    for(int i=1;i<len;i++) if(lengths[i]>lengths[index]) index=i; //Find max

    
    palindrome.first=(index-lengths[index]+1)/2;
    palindrome.second=(index+lengths[index]+1)/2;
    return palindrome;
}

int main(int argc, const char * argv[]) //Driver
{

    pair<int, int> palindrome;
    palindrome=longestPalindrome("abcbabcbabcba");
    cout<<"Found between indices: "<<palindrome.first<<"  "<<palindrome.second;
    return 0;
}