Cod sursa(job #712556)

Utilizator mottyMatei-Dan Epure motty Data 13 martie 2012 16:24:50
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <string>

using namespace std;

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

const int N = 2000005;

int n;
string s;

int v[N];

void read()
{
  string auxStr;
  in >> auxStr;

  s += 'O';
  for (int i = 0; i < (int)auxStr.size(); ++i) {
    s += auxStr[i];
    s += 'O';
  }

  n = s.size();
}

void solve()
{
  int bestEnd = -1;
  int bestCenter = 0;

  for (int i = 0; i < n; ++i)
    if (bestEnd <= i) {
      int j;
      for (j = 0; i+j < n && i-j >= 0 && s[i+j] == s[i-j]; ++j);
      v[i] = j;
      if (i + j - 1 > bestEnd) {
        bestEnd = i + j - 1;
        bestCenter = i;
      }
    }
    else {
      int opElement = bestCenter - (i - bestCenter);

      if (i + v[opElement] - 1 < bestEnd)
        v[i] = v[opElement];
      else {
        int j;
        for (j = bestEnd - i; i+j < n && i-j >= 0 && s[i+j] == s[i-j]; ++j);
        v[i] = j;

        if (i + j - 1 > bestEnd) {
          bestEnd = i + j - 1;
          bestCenter = i;
        }
      }
    }
}

int getAnswer()
{
  int res = 0;

  for (int i = 0; i < n; ++i) {
    res += v[i]/2;
  }

  return res;
}

int main()
{
  read();
  solve();

  out << getAnswer() << "\n";

  return 0;
}