Cod sursa(job #2289073)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 24 noiembrie 2018 10:57:15
Problema PScPld Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s[2000004];
int p[2000004];

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    s[0] = '#';
    int i=1;
    int ok=0;
    char ci;
    while(ok == 0)
    {
        scanf("%c", &ci);
        if(ci == '\0' || ci== '\n')
            ok=1;
        else{
            s[i] = ci;
            s[++i] = '#';
            i++;
        }
    }
    int n = strlen(s);
    int c=0, R=0, nr=0;
    for(int i=1; i<=n-1; i++)
    {
        int simi=c-(i-c);
        p[i] = 0;
        //if(R > i)
     //   {
       //     p[i] = min(R-i, p[simi]);
      //  }
        while(s[i+1+p[i]] == s[i-1-p[i]])
        {
            if(s[i+1+p[i]] == '#')
                nr++;
            p[i]++;
        }
        if(i+p[i] > R)
        {
            R = i+p[i];
            c = i;
        }
    }
    printf("%d", nr);
    return 0;
}