Pagini recente » Cod sursa (job #433801) | Cod sursa (job #2878900) | Cod sursa (job #5160) | Cod sursa (job #1647333) | Cod sursa (job #1227500)
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <fstream>
#include <cstring>
#include <bitset>
#include <stack>
#include <vector>
#include <map>
#include <set>
#define per pair<int,int>
#define x first
#define y second
#define DN 200000
#define DM 2000
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char C[2000020],A[1000005];
int n,i,k,P[2000020],id=1,mx=2;
long long rez;
void read(){
f>>A;
n=strlen(A);
C[0]='$'; C[1]='#';
k = 2;
for(int i=0 ; i<n ; ++i){
C[k++] = A[i];
C[k++] = '#';
}
C[k]='\0';
}
int main()
{
read();
P[1]=1;
n=strlen(C);
for(i=2;i<n;i++)
{
P[i]= ((mx>i) ? min(P[2*id-i],mx-i):1 );
while(C[i+P[i]]==C[i-P[i]]) /// extindem palindromul cu centrul in i
P[i]++;
if(P[i]+i>mx)
{
mx=P[i]+i;
id=i;
}
}
for(i=1;i<n;i++){
if(C[i]=='#')
rez+=(P[i]-1)/2;
else
rez+=P[i]/2;
}
cout<<rez;
g<<rez<<'\n';
return 0;
}