Cod sursa(job #2608159)

Utilizator alex_benescuAlex Ben alex_benescu Data 30 aprilie 2020 18:15:25
Problema PScPld Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <iostream>
#define L 1000003
using namespace std;
int s[L], d1[L], d2[L];

int main() {
  freopen("pscpld.in", "r", stdin);
  freopen("pscpld.out", "w", stdout);
  long long rez;
  int i=0, n, k, l, r;
  char c;

  while ( (c = fgetc(stdin))!='\n')
    s[i++] = c;
  n = i;

  for (i = 0, l = 0, r = -1; i < n; i++) {
    k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
    while (0 <= i - k && i + k < n && s[i - k] == s[i + k])
      k++;
    d1[i] = k--;
    if (i + k > r) {
      l = i - k;
      r = i + k;
    }
  }

  for (i = 0, l = 0, r = -1; i < n; i++) {
    k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
    while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k])
      k++;
    d2[i] = k--;
    if (i + k > r) {
      l = i - k - 1;
      r = i + k ;
    }
  }

  rez = 0;
  for (i = 0; i < n; i++)
    rez +=  d1[i] + d2[i];

  printf("%lld\n", rez);
  return 0;
}