Pagini recente » Cod sursa (job #598102) | Cod sursa (job #1193992) | Cod sursa (job #751602) | Cod sursa (job #706248) | Cod sursa (job #2701218)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
std::ifstream fin("pscpld.in");
std::ofstream fout("pscpld.out");
int main(){
std::string s, x = "#";
fin >> s;
for(int i=0; i<s.size(); i++){
x.push_back(s[i]);
x.push_back('#');
}
int lps[x.size()] = {};
lps[0] = 1;
int left=0, right=-1;
for(int i=1, k; i<x.size(); i++){
if(right >= i) k = std::min(lps[left + (right - i)], right - i + 1);
else k = 1;
while(0 <= i - k and i + k < x.size() and x[i-k] == x[i+k])
k ++;
lps[i] = k--;
if(i + k > right){
right = i + k;
left = i - k;
}
}
int ans = 0;
for(int i=0; i<x.size(); i++)
ans = ans + lps[i] / 2;
fout << ans << '\n';
return 0;
}