Cod sursa(job #1889302)

Utilizator DevilOnFieldTudor Horia Niculescu DevilOnField Data 22 februarie 2017 17:50:42
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <iostream>
#include <cstring>
 
using namespace std;
 
ifstream re ("pscpld.in");
ofstream we ("pscpld.out");
 
const int MAXN = 1000005;
char s[2 * MAXN];
int p[2 * MAXN], n;
 
int main ()
{
    re >> s;
    n = strlen(s);
    long long sum = n;
    for(int i = n  - 1; i >= 0; i--) {
    s[i * 2 + 1] = s[i];
    s[i * 2 + 2] = '#';
    }
    s[0] = '#';
     
    n = n * 2;
    int r = 0;
    int m = 0;
    p[0] = 0;
    p[n] = 0;
    for(int i = 1; i < n; i++) {
    int j;
    //cout << " m = " << m << " r = " << r << " i = " << i << " j = " << j << ' ';
    if(i < r) {
        j = 2 * m - i;
        //cout << " jiji:" << j; 
        if(j >= 0 && i + p[j] < r) {
        p[i] = p[j];
        //cout << "  CAZ 1";
        } else {
            j = r - i;
        int aux = 2 * m - r;
        //cout << " gaf:" << aux;
        while((i + j <= n) && (i - j  >= 0) && (s[i + j] == s[i - j])) {
            j++; //cout << " BAU:" << j;
        }
        j--;
        m = i;
        r = i + j;
        p[i] = j;
        //cout << "  CAZ 2";
        }
    } else {
        j = 0;
        while(i + j <= n && i - j >= 0 && s[i + j] == s[i - j]) {
        j++;
        }
        j--;
        m = i;
        r = i + j;
        p[i] = j;
        ////cout << "  CAZ 3";
    }
    ////cout << endl;
    sum += p[i] / 2;
    }
    /*      
    for(int i = 0; i <= n; i++) {
    we << s[i] << ' ';
    }
    we << endl;
    for(int i = 0; i <= n; i++) {
    we << p[i] << ' ';
    }
    */
    we << sum;
 
    re.close();
    we.close();
 
    return 0;
}