Pagini recente » Borderou de evaluare (job #2783443) | Cod sursa (job #1955978) | Rating Horatiu Andrei Cheval (horatiucheval2) | Cod sursa (job #2508383) | Cod sursa (job #940608)
Cod sursa(job #940608)
#include <fstream>
using namespace std;
int N;
char s[1000011];
char v[2000011];
int dp[2000011];
void Citire ()
{
ifstream fin ("pscpld.in");
fin >> s;
for (N = 0; s[N] != '\0'; N++)
{
v[N << 1] = s[N];
v[(N << 1) + 1] = '$';
}
N = (N << 1) - 1;
v[N] = '\0';
fin.close ();
}
long long Business ()
{
long long S = 0;
dp[0] = 0;
int poz = 0, curent;
for (int i = 1; i < N; i++)
{
if (i >= poz + dp[poz])
{
curent = 1;
for (; i + curent < N && i - curent >= 0; curent++)
if (v[i + curent] != v[i - curent]) break;
curent--;
}
else
{
curent = min (dp[(poz << 1) - i], poz + dp[poz] - i);
if (i + curent == poz + dp[poz])
{
for (++curent; curent < N && i - curent >= 0; curent++)
if (v[i + curent] != v[i - curent]) break;
curent--;
}
}
dp[i] = curent;
if (i + dp[i] >= poz + dp[poz]) poz = i;
if (v[i] != '$') S += dp[i] >> 1;
else S += (dp[i] + 1) >> 1;
}
return S + (N >> 1) + 1;
}
void Scriere ()
{
ofstream fout ("pscpld.out");
fout << Business ();
fout.close ();
}
int main ()
{
Citire ();
Scriere ();
return 0;
}