Cod sursa(job #2089448)

Utilizator GoogalAbabei Daniel Googal Data 16 decembrie 2017 15:42:31
Problema PScPld Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream in("pscpld.in");
ofstream out("pscpld.out");

int const nmax = (int) 1e6;

char sir[2 * nmax + 2];
int dp[2 * nmax + 1];
int n;
long long nr;

int main() {
  in >> sir;
  n = strlen(sir);

  for(int i = n - 1; i >= 0; i--) {
    sir[2 * i + 1] = sir[i];
    sir[2 * i + 2] = '*';
  }
  sir[0] = '*';
  sir[2 * n] = '*';
  n = 2 * n;
  //cout << sir;

  int c = 1;
  int dr = c;
  for(int i = 0; i <= n; i++) {
    if(i < dr)
      dp[i] = min(dp[2 * c - i], dr - i);
    else
      dp[i] = 1;

    while(sir[i - dp[i]] == sir[i + dp[i]])
      dp[i]++;

    if(dr < i + dp[i]) {
      c = i;
      dr = i + dp[i];
    }
    nr += 1LL * (dp[i] / 2);
  }

  out << nr << '\n';

  in.close();
  out.close();
  return 0;
}