Pagini recente » Cod sursa (job #13177) | Cod sursa (job #1740363) | Cod sursa (job #601702) | Cod sursa (job #1393016) | Cod sursa (job #2566670)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream in ("pscpld.in");
ofstream out("pscpld.out");
string s;
int n, rez;
int main()
{
in>>s;
n=s.size();
vector <int> d1(n);
for(int i=0, l=0, r=-1; i<n; i++)
{
int strt=(i>r) ? 1 : min(r-i, d1[l+r-i]);
while(i+strt<n&&i-strt>=0&&s[i+strt]==s[i-strt])
strt++;
d1[i]=(--strt);
if(r>i+strt)
l=i-strt, r=i+strt;
rez+=d1[i]+1;
//cout<<d1[i]<<" ";
}
//cout<<"\n\n";
vector <int> d2(n);
for(int i=1, l=0, r=-1; i<n; i++)
{
int strt=(i>r) ? 0 : min(r-i, d2[l+r-i-1]);
while(i+strt<n&&i-strt-1>=0&&s[i+strt]==s[i-strt-1])
strt++;
d2[i]=strt;
if(r>i+strt)
l=i-strt, r=i+strt;
rez+=d2[i];
//cout<<d2[i]<<" ";
}
out<<rez;
return 0;
}