Cod sursa(job #1856825)

Utilizator alexmisto342Turdean Alexandru alexmisto342 Data 25 ianuarie 2017 14:54:18
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#define ll long long
#define LL long long
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s,t;
int n,i,j,maxi,idx,l[3000000],rasp;
int main ()
{
    fin >> t;
    s='$';
    for(i = 0; i < t.size();i++)
        s = s + t[i] + '$';
    for(i = 1; i < s.size(); i++)
    {
        if(i <= maxi)
            l[i] = min(maxi - i, l[idx * 2 - i]);
        while(l[i] + 1 + i < s.size() && i - l[i] - 1 >= 0 && s[ l[i] + i + 1 ] == s[ i - l[i] - 1 ])
            l[i]++;
        if(l[i] > maxi)
            maxi = l[i], idx = i;
        rasp += (l[i] + 1) / 2;
    }
    cout<<rasp;
    return 0;
}