Pagini recente » Cod sursa (job #746384) | Cod sursa (job #150706) | Cod sursa (job #809480) | Cod sursa (job #2649565) | Cod sursa (job #2791355)
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
const int DIM = 1e6+5;
char v[DIM];
char s[2*DIM];
int builds(int len) {
int newlen = 0;
s[0]='#';
for (int i=0; i<=len; i++)
s[++newlen] = v[i], s[++newlen] = '#';
return newlen;
}
int main() {
f >> v;
int len = strlen(v)-1;
len = builds(len);
vector<int> dis(len+1,0);
long long npal = 0;
for (int i = 0, r=-1, c=-1; i <= len; i++) {
if(i>r)
dis[i]=1;
else
dis[i]=min(dis[c-(i-c)],r-i);
while (i-dis[i]>=0 && i+dis[i]<=len && s[i-dis[i]]==s[i+dis[i]])
dis[i]++;
if (i+dis[i]-1>r)
r=i+dis[i]-1, c=i;
npal+=dis[i]/2;
}
g<<npal;
return 0;
}