Cod sursa(job #2079244)

Utilizator GoogalAbabei Daniel Googal Data 30 noiembrie 2017 20:29:20
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

const int NMAX = 1000000 + 100;

int n;
int lung[NMAX * 2];
long long res;
string s1, s;

int main()
{
  in >> s1;
  n = s1.size();

  for(int i = 1; i <= n; i++) {
    s[2 * i - 1] = '#';
    s[2 * i] = s1[i - 1];
  }
  s[2 * n + 1] = '#';
  n = n * 2 + 1;

  int j = 0;
  for(int i = 1; i <= n; i++) {
    //cout << s[i] << ' ';
    if(i < lung[j] + j)
      lung[i] = min(lung[2 * j - i], j - i + lung[j]);
    else
      lung[i] = 1;

    while(lung[i] < i && s[i - lung[i]] == s[i + lung[i]])
      lung[i]++;
    res += 1LL * (lung[i] / 2);
    if(j + lung[j] < i + lung[i])
      j = i;
  }

  //cout << "here";
  out << res << '\n';

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