Pagini recente » Cod sursa (job #1373991) | Cod sursa (job #1947174) | Cod sursa (job #1698997) | Cod sursa (job #1255557) | Cod sursa (job #2480208)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int mij, sum, n, st, jdr, jst, dr, k = -1;
int v[4000005];
char c[4000005];
string s;
int main()
{
cin >> s;
n=s.size();
n *= 2;
for(int i = 0; i <= n; i += 2)
{
c[i] = '*';
c[i+1] = s[++k];
}
for(int i = 1; i <= 2 * n; i++)
{
if(i <= dr)
{
mij = st + dr - i;
v[i] = min(v[mij], mij - st + 1);
jdr = i + v[i];
jst = i - v[i];
while(jst >= 0 && jdr <= n && c[jdr] == c[jst])
{
jdr++;
jst--;
v[i]++;
}
if(dr < i + v[i] - 1)
{
dr = i + v[i] - 1;
st = i - v[i] + 1;
}
}
else
{
jdr=i,jst=i;
while(jst >= 0 && jdr <= n && c[jdr] == c[jst])
{
jdr++;
jst--;
v[i]++;
}
dr = i + v[i] - 1;
st = i - v[i] + 1;
}
}
for(int i = 1; i <= n; i++)
sum += v[i] / 2;
cout << sum;
return 0;
}