Cod sursa(job #1344494)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 16 februarie 2015 19:25:50
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int V[2000010];
string A, S;

int main()
{
    fin >> A;
    S += "@";
    for (int i = 0; i < A.size(); i++)
    {
        S += "+";
        S += A[i];
    }
    S += "+@";

    int r = 0, c = 0;
    for (int i = 1; i < S.size() - 1; i++)
    {
        if (i < r)
        {
            V[i] = min(r - i, V[c * 2 - i]);
        }
        while (i - V[i] - 1 > 0 &&
                i + V[i] + 1 < S.size() &&
                S[i - V[i] - 1] == S[i + V[i] + 1]) V[i] += 1;

        if (r < V[i] + i)
        {
            r = V[i] + i;
            c = i;
        }
    }

    long long nr = 0;
    for (int i = 1; i < S.size(); i++)
    {
        nr += (V[i] + 1) / 2;
    }
    fout << nr << '\n';
    fout.close();
    return 0;
}