Pagini recente » Cod sursa (job #1792110) | Istoria paginii runda/cerculdeinfo-lectia9-cuplaj_flux | Cod sursa (job #1721270) | Cod sursa (job #1673259) | Cod sursa (job #1648623)
#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);
}