Cod sursa(job #843258)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 17:21:36
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <string>
#include <iostream>
 
const int MAX_N = 1001000;
 
std::ifstream fin;
std::ofstream fout;
char s[2*MAX_N];
int l[2*MAX_N];
int N;
long long result;
 
inline int min(int a, int b) {
    return a > b ? b : a;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
 
int main(int argc, char const *argv[]) {
    fin.open("pscpld.in");
    char ch;
    s[++N] = '@';
    while (1) {
        fin.get(ch);
        if (ch == '\n')
            break;
        s[++N] = ch;
        s[++N] = '@';
    }
 
    fin.close();

 
    int best = 0;
    for (int i = 1; i <= N; ++i) {
      if (best + l[best] >= i) {
        l[i] = min(best + l[best] - i, l[2 * best - i]);
      }
      while (i - l[i] - 1 >= 0 && i + l[i] + 1 <= N && 
             s[i - l[i] - 1] == s[i + l[i] + 1]) {
        ++l[i];
      }
      if (i + l[i] > best + l[best]) {
        best = i;
      }
    }
 
    result = 0;
    for (int i = 1; i <= N; ++i) {

      if (i % 2 == 0)
        result += (l[i] + 1) / 2;
      else
        result += l[i] / 2;
    }
 
    fout.open("pscpld.out");
    fout << result;
    fout.close();
    return 0;
}