Cod sursa(job #1780701)

Utilizator Kira96Denis Mita Kira96 Data 16 octombrie 2016 15:11:22
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cassert>
#include <cstring>
#include <queue>
#include <algorithm>
#include <bitset>
#include <set>
#include <cmath>
#include <iomanip>
#include <map>
#include <stack>
#include <vector>
#include <bitset>
#include <fstream>
// #include <iostream>

using namespace std;

#define f cin
#define g cout
#define FOR(i, a, n) for (int i = a; i <= n; ++i)
#define ROF(i, a, n) for (int i = n; i >= a; i--)
#define FIT(i, v) for (auto &i : v)
#define pb push_back
#define mp make_pair
#define mt make_touple
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef pair<int,int> pii;
const int mod = 1000000007;
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}
#define sq(x) x * x

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

const int N = 2000100;

char s[N], a[N];
int n, m, D[N];
ll sol;

int main () {
    cin >> (s + 1);
    n = strlen(s + 1);
    
    for (int i = 1; i <= n; ++i) {
      a[2 * i] = s[i];
      a[2 * i - 1] = ' ';
    }
    m = 2 * n + 1;
    a[m] = ' ';
    
    int centru = 0;
    for (int i = 1; i <= m; ++i) {
      if (i <= centru + D[centru] - 1) {
	int sim = centru - (i - centru);
	D[i] = min(D[sim], (centru + D[centru] - 1 - i + 1));
      }
      while (a[i + D[i]] && a[i + D[i]] == a[i - D[i]]) {
	++D[i];
      }
      if (i + D[i] > centru + D[centru]) {
	centru = i;
      }
      sol += D[i] / 2;
      //      cerr << D[i] - 1 << " ";
    }
    
    cout << sol;
    return 0;
}