Pagini recente » Cod sursa (job #2741860) | Cod sursa (job #1311562) | Cod sursa (job #3262890) | Cod sursa (job #2547801) | Cod sursa (job #2791352)
#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);
int 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)],dis[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;
}
cout<<npal;
}