Pagini recente » Cod sursa (job #2873189) | Cod sursa (job #1650345) | Cod sursa (job #283804) | Cod sursa (job #573124) | Cod sursa (job #712804)
Cod sursa(job #712804)
#include<fstream>
#include<algorithm>
#define n_max 999999999
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char S[n_max];
int Lung[n_max];
int N;
long long sol;
void citeste()
{
while (fin >> S[2 * N + 1])
N ++;
fin.close();
}
void rezolva()
{
int idx = 1;
for (int i=1; i<2*N; ++i)
{
if (idx + Lung[idx] - 1 < i)
Lung[i] = i&1;
else
Lung[i] = min(Lung[idx - (i - idx)], idx + Lung[idx] - i );
int j = Lung[i] + 1;
while (i - j >= 1 && i + j < 2*N && S[i-j] == S[i+j])
j+=2;
j -= 2;
Lung[i] = j + 1;
if ( i + Lung[i] > idx + Lung[idx])
idx = i;
sol += (Lung[i] + 1) / 2;
}
}
void afiseaza()
{
fout<<sol<<'\n';
fout.close();
}
int main(void)
{
citeste();
rezolva();
afiseaza();
return 0;
}