Cod sursa(job #1684360)

Utilizator BrandonChris Luntraru Brandon Data 10 aprilie 2016 23:35:10
Problema PScPld Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>

#define LL long long
using namespace std;

const int MaxLng = 2000005;

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

string str;

int lng[MaxLng];
int n, last;
LL ans;

int main() {
  cin >> str;
  n = 2 * str.size();
  str = '0' + str;
  lng[0] = 1;

  for(int i = 1; i <= n; ++i) {
    if(last + lng[last] > i) {
      lng[i] = min(lng[2 * last - i], lng[last]);
    }
    else {
      lng[i] = (i % 2 == 0);
    }

    while(i + lng[i] < n and i - lng[i] > 0 and str[(i + lng[i] + 1) / 2] == str[(i - lng[i] - 1) / 2]) {
      lng[i] += 2;
    }

    if(i + lng[i] > last + lng[last]) {
      last = i;
    }

    ans += (lng[i] + 1) / 2;
  }

  cout << ans << '\n';
  return 0;
}