Pagini recente » Cod sursa (job #1608689) | Cod sursa (job #2552048) | Cod sursa (job #1109881) | Cod sursa (job #409100) | Cod sursa (job #2586405)
#include <bits/stdc++.h>
#define DIM 2000010
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
char s[DIM],v[DIM];
int p[DIM];
int n,m,i;
long long manacher (){
m = strlen (s+1), n = 0;
v[++n] = '*';
for (i=1;i<=m;i++){
v[++n] = s[i];
v[++n] = '*';
}
/// p[i] - cu cat se poate extinde un palindrom cu centrul in i
int c = 0, Left = 0, Right = 0;
long long sol = 0;
for (i=1;i<=n;i++){
if (i > Right){
/// extind cat pot de la i
p[i] = 1;
Left = Right = c = i;
while (Left > 1 && Right < n && v[Left-1] == v[Right+1]){
p[i]++;
Left--, Right++;
}
} else {
int mirror = c - (i - c);
p[i] = min (p[mirror], Right - i + 1);
/// acum incercam sa extindem
int st = i - p[i];
int dr = i + p[i];
while (st >= 1 && dr <= n && v[st] == v[dr]){
p[i]++;
st--, dr++;
}
if (i + p[i] - 1 > Right){
c = i;
Left = i - p[i] + 1;
Right = i + p[i] - 1;
}
}
//maxi = max (maxi,p[i]);
sol += p[i] / 2;
}
return sol;
}
int main (){
fin>>s+1;
fout<<manacher();
// for (i=1;i<=n;i++)
// fout<<p[i]<<" ";
return 0;
}