Cod sursa(job #1258258)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 8 noiembrie 2014 17:31:50
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
#define MAX 13
char sir[MAX];
long long rez;
int n, par[MAX], imp[MAX], iimp=1, lgimp=0, ipar=0, lgpar=0;
int main()
{
    int i;
    fin>>sir+1; sir[0]='A';
    n = strlen(sir+1);
    imp[1] = 0; par[1] = 0;
    for(i=2; i<=n; i++){
        if(i<iimp+lgimp){
            if(i+imp[2*iimp-i]<iimp+lgimp)
                imp[i] = imp[2*iimp-i];
            else
                imp[i]=iimp+lgimp-i;
        }
        while(sir[i-imp[i]]==sir[i+imp[i]]) imp[i]++;
        imp[i]--;
        if(i+imp[i]>iimp+lgimp){
            iimp = i; lgimp = imp[i];
        }
        if(sir[i]==sir[i-1]){
            rez++;
            if(i<ipar+lgpar){
                if(i+par[2*ipar-i-1]<ipar+lgpar)
                    par[i] = par[2*ipar-i-1];
                else
                    par[i]=ipar+lgpar-i;
            }
            while(sir[i-par[i]-1]==sir[i+par[i]]) par[i]++;
            par[i]--;
            if(i+par[i]>ipar+lgpar){
                ipar = i; lgpar = par[i];
            }
        }
    }
    for(i=1; i<=n; i++)
        rez = rez + 1 + par[i]+imp[i];
    fout<<rez;
    return 0;
}