Pagini recente » Cod sursa (job #402786) | Cod sursa (job #1718712) | Cod sursa (job #2867730) | Cod sursa (job #1442735) | Cod sursa (job #1732437)
#include <fstream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;
string problemName = "pscpld";
string inFile = problemName+".in";
string outFile = problemName+".out";
ifstream fin(inFile.c_str());
ofstream fout(outFile.c_str());
const int N = 1e6+5;
string s,ax;
int p[2*N];
int main(){
int n,i;
fin>>ax;
s += '@';
s += '#';
n = ax.size();
for(i = 0;i < n;i++){
s += ax[i];
s += '#';
}
s += '$';
int mirr,R,C;
R = C = 0;
n <<= 1;
n++;
long long unsigned sum = 0;
for(i = 1;i <= n;i++){
mirr = 2*C-i;
if(R > i){
p[i] = min(R-i, p[mirr]);
}
while(s[i+1+p[i]] == s[i-1-p[i]]){
p[i]++;
}
if(i+p[i] > R){
R = i + p[i];
C = i;
}
sum += (p[i]+1)/2;
}
fout<<sum;
return 0;
}