Pagini recente » Cod sursa (job #1020317) | Cod sursa (job #262290) | Cod sursa (job #1090530) | Cod sursa (job #921731) | Cod sursa (job #3170042)
#include <iostream>
#include <fstream>
#include <cstring>
#define N 1000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[N], c[2*N];
int dims, dimc = -1, st, dr;
int dist[2*N];
long long result;
///Manacher's algorithm - used to find the longest palindromic substring in any string
int main() {
fin >> s; /// abaaac
dims = strlen(s);
dimc ++;
c[dimc] = '!';
dimc ++;
c[dimc] = '*'; /// *a*b*a*a*a*c
for(int i = 0; i < dims; i++)
{
dimc ++;
c[dimc] = s[i];
dimc++;
c[dimc] = '*';
}
dimc++;
c[dimc] = '?';
dimc++;
c[dimc] = 0;
st = -1;
dr = -1;
for(int i = 0; i < dimc; i++)
{
if(i > dr) dist[i] = 0;
else
dist[i] = min(dr - i, dist[st+dr-i]);
while(c[dist[i]+i] == c[i - dist[i]])
dist[i] ++;
dist[i] --;
if(i+dist[i] > dr)
{
st = i - dist[i];
dr = i + dist[i];
}
}
for(int i = 0; i < dimc; i ++)
result += (dist[i] + 1)/2;
fout << result;
return 0;
}