Pagini recente » Cod sursa (job #2751916) | Cod sursa (job #864372) | Cod sursa (job #1410971) | Cod sursa (job #748918) | Cod sursa (job #2489311)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int mij,rasp,n,st,j,j2,dr,k = -1;
int v[2000005];
char s[2000005],s2[1000001];
int main()
{
f.getline(s2,1000001);
n = strlen(s2);
n *= 2;
for(int i = 0; i <= n; i += 2)
{
s[i] = '*';
s[i + 1] = s2[++k];
}
for(int i = 1; i <= 2 * n; ++i)
{
if(i <= dr)
{
mij = st + dr - i;
v[i] = min(v[mij],mij - st + 1);
j = i + v[i];
j2 = i - v[i];
while(j2 >= 0 && j <= n && s[j] == s[j2])
{
j++;
j2--;
v[i]++;
}
if(dr < i + v[i] - 1)
{
dr = i + v[i] - 1;
st = i - v[i] + 1;
}
}
else
{
j = i;
j2 = i;
while(j2 >= 0 && j <= n && s[j] == s[j2])
{
j++;
j2--;
v[i]++;
}
dr = i + v[i] - 1;
st = i - v[i] + 1;
}
rasp += v[i] / 2;
}
g << rasp;
return 0;
}