Cod sursa(job #1648623)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 11 martie 2016 11:00:16
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LOGMAX 20
#define NMAX 300023
using namespace std;
int n=-1;
char ch[2*NMAX],ch2[NMAX],prop;
int suffix[NMAX][LOGMAX],l2[NMAX];
struct str
{
    int left;
    int right;
    int p;
}v[NMAX];
int comp(const str &a,const str &b)
{
    if(a.left!=b.left) return a.left<b.left;
    return a.right<b.right;
}
int mirror(int p)
{
    return (2*n-p-1);
}
int egal(int p1,int p2,int p3,int p4)
{
    if(p2-p1+1!=p4-p3+1) return 0;
    int l=l2[p2-p1+1];
    int l1=suffix[p1][l],r1=suffix[p2-(1<<l)+1][l];
    int l3=suffix[p3][l],r2=suffix[p4-(1<<l)+1][l];
    if(l1==l3&&r1==r2) return 1;
    return 0;
}
int main()
{
    freopen ("pscpld.in","r",stdin);
    freopen ("pscpld.out","w",stdout);
    l2[1]=0;
    for(int i=2;i<=NMAX;i++)
    {
        l2[i]=l2[i-1];
        if((i&(i-1))==0) l2[i]++;
    }
    scanf("%s",ch2);
    int marmar=strlen(ch2);
    for(int i=0;i<marmar;i++)
    {
        ch[++n]='|';
        ch[++n]=ch2[i];
    }
    ch[++n]='|';
    ++n;
    int p=2*n;
    for(int i=0;i<n;i++) ch[p-i-1]=ch[i];
    for(int i=0;i<p;i++) suffix[i][0]=(int)ch[i];
    for(int j=1;j<=l2[p];j++)
    {
        for(int i=0;i<p;i++)
        {
            v[i].left=suffix[i][j-1];
            if(i+(1<<(j-1))>=p) v[i].right=-1;
            else v[i].right=suffix[i+(1<<(j-1))][j-1];
            v[i].p=i;
        }
        sort(v,v+p,comp);
        suffix[v[0].p][j]=1;
        int cnt=1;
        for(int i=1;i<p;i++)
        {
            if((v[i].left!=v[i-1].left)||(v[i].right!=v[i-1].right)) ++cnt;
            suffix[v[i].p][j]=cnt;
        }
    }
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int s=0,e=n,rasp=0;
        while(s<=e)
        {
            int mij=(s+e)/2;
            if(i-mij<0)
            {
                e=mij-1;
                continue;
            }
            if(i+mij>=n)
            {
                e=mij-1;
                continue;
            }
            if(egal(i,i+mij,mirror(i),mirror(i-mij)))
            {
                rasp=mij;
                s=mij+1;
            }
            else e=mij-1;
        }
        if(ch[i]=='|') sum+=rasp/2;
        else sum+=(rasp/2)+1;
    }
    printf("%d\n",sum);
}