Cod sursă (job #569067)

#include <bits/stdc++.h>
#define NMAX 500005
using namespace std;
/*******************************************************/
/// INPUT / OUTPUT
ifstream f("bart.in");
ofstream g("bart.out");
/*******************************************************/
/// GLOBAL DECLARATIONS

char s[NMAX];
int answer, n;
int predecesor[NMAX];
/*******************************************************/
///-----------------------------------------------------------------
inline void readInput()
{
    f >> (s + 1);
    n = strlen(s+1);
}
///-----------------------------------------------------------------
int getPrecedent(int index)
{
    int pos = index;
    while(s[pos] != s[predecesor[index - 1] + 1] && index > 0)
    {
        index = predecesor[index - 1];
    }
    return index;
}
///-----------------------------------------------------------------
inline void Solution()
{

    predecesor[1] = 0;
    for(int i = 2 ; i <= n; ++ i)
    {
        if(s[i] == s[predecesor[i -1] + 1]) predecesor[i] = predecesor[i-1] + 1;
        else
        {
         predecesor[i] = getPrecedent(i);
        }
    }
    answer = n - predecesor[n];
}
///-----------------------------------------------------------------
inline void Output()
{
    for(int i = 1 ; i <= answer ; ++i) g << s[i];
}
///-----------------------------------------------------------------
int main()
{
    readInput();
    Solution();
    Output();
    return 0;
}