Cod sursa(job #2791253)

Utilizator Robert.BrindeaBrindea Robert Robert.Brindea Data 30 octombrie 2021 11:51:41
Problema PScPld Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int MAXN = 1000003;

char s[2*MAXN], temp[MAXN];
int n, c, r, p[2*MAXN];

void hashtag()
{
    s[n++] = '#';
    int len = strlen(temp);
    for(int i = 0; i < len; i++)
        s[n++] = temp[i], s[n++] = '#';
}

int main()
{
    fin >> temp;
    hashtag();
    for(int i = 0; i < n; i++)
    {
        int sim = c-(i-c);
        if(i <= r)
            p[i] = min(r, p[sim]);
        while(i+p[i]+1 < n && i-p[i]-1 >= 0 && s[i+p[i]+1] == s[i-p[i]-1])
            p[i]++;
        if(i+p[i] > r)
        {
            c = i;
            r = i+p[i];
        }
    }
    int rez = strlen(temp);
    for(int i = 0; i < n; i++)
        rez += (p[i] > 1);
    fout << rez;
    return 0;
}