Cod sursa(job #1414759)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 2 aprilie 2015 23:01:25
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>

#include <cstring>
using namespace std;

const int MAX_N = 1000002;

int N;
int D[2 * MAX_N];
long long ans;
char s[2 * MAX_N], t[MAX_N];

int main() {
    ifstream f("pscpld.in");
    ofstream g("pscpld.out");

    t[0] = s[0] = ' ';
    f >> (t + 1);

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

    for(int i = 1, C = 0, L = 0, R = 0; i <= N; ++i) {
        if(i <= R) {
            int j = 2 * C - i;

            if(j - D[j] > L) {
                D[i] = D[j];
            }
            else {
                D[i] = j - L;

                while(i - D[i] - 1 >= 1 && i + D[i] + 1 <= N && s[i - D[i] - 1] == s[i + D[i] + 1]) {
                    ++D[i];
                }
            }
        }
        else {
            D[i] = 0;
            while(i - D[i] - 1 >= 1 && i + D[i] + 1 <= N && s[i - D[i] - 1] == s[i + D[i] + 1]) {
                ++D[i];
            }
        }

        if(i + D[i] > R) {
            C = i;
            R = i + D[i];
            L = i - D[i];
        }
    }

    for(int i = 1; i <= N; ++i) {
        if(s[i] == '#') {
            ans += D[i] / 2;
        }
        else {
            ans += D[i] / 2 + 1;
        }
    }

    g << ans << "\n";

    f.close();
    g.close();

    return 0;
}