Cod sursa(job #1227430)

Utilizator o_micBianca Costin o_mic Data 10 septembrie 2014 15:19:15
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

string create_aux(string s)
{
    string res;
    int i, n = s.length();
    if(!n)
        res = "^$";
    else
    {
        res = "^";
        for(i = 0 ; i < n ; i++)
            res += "#" + s.substr(i, 1);
    }
    res += "#$";
    return res;
}

int main()
{
    string s, T;
    int n, mid, r, aux, sum = 0;
    fstream f("pscpld.in", ios::in);
    fstream g("pscpld.out", ios::out);
    f >> s;
    T = create_aux(s);
    //cout << T;
    n = T.length();
    int *p = new int[n];
    mid = r = 0;
    for(int i = 1 ; i < n-1 ; i++)
    {
        aux = mid - (i - mid);
        if(r > i)
            p[i] = min(r - i, p[aux]);
        else
            p[i] = 0;
        while(T[i + 1 + p[i]] == T[i - 1 - p[i]])
            p[i]++;
        //cout << p[i] << " ";
        if(i + p[i] > r)
        {
            r = i + p[i];
            mid = i;
        }
        sum += (p[i] + 1) / 2;
    }
    g << sum;
    return 0;
}