subsecventa

/// A C program to implement Manacher’s Algorithm
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
ofstream g("subsecventa.out");
char text[100001];

void findLongestPalindromicString()
{
    int N=strlen(text);
    if(N==0)
        return;
    N=2*N+1; ///Position count
    int L[N]; ///LPS Length Array
    L[0]=0;
    L[1]=1;
    int C=1; ///centerPosition
    int R=2; ///centerRightPosition
    int i=0; ///currentRightPosition
    int iMirror; ///currentLeftPosition
    int maxLPSLength=0;
    int maxLPSCenterPosition=0;
    int start=-1;
    int end=-1;
    int diff=-1;
    ///Uncomment it to print LPS Length array
    ///printf("%d %d ", L[0], L[1]);
    for(i=2;i<N;++i)
    { ///get currentLeftPosition iMirror for currentRightPosition i
        iMirror =2*C-i;
        L[i]=0;
        diff=R-i;
        if(diff>0) ///If currentRightPosition i is within centerRightPosition R
            L[i]=min(L[iMirror],diff);
        ///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
        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)  /// Track maxLPSLength
        {
            maxLPSLength=L[i];
            maxLPSCenterPosition=i;
        }
        ///If palindrome centered at currentRightPosition i
        ///expand beyond centerRightPosition R,
        ///adjust centerPosition C based on expanded palindrome.
        if(i+L[i]>R)
        {
            C=i;
            R=i+L[i];
        }
    }
    if(maxLPSLength>1)
    {
        start=(maxLPSCenterPosition-maxLPSLength)/2;
        end=start+maxLPSLength-1;
        g<<maxLPSLength<<'\n';
        for(i=start;i<=end;i++)
            g<<text[i];
    }
    else
        g<<1<<'\n'<<text[0];
}

int main()
{
    ifstream f("subsecventa.in");
    f>>text;
    findLongestPalindromicString();
    return 0;
}