Pagini recente » Cod sursa (job #1190720) | Cod sursa (job #1930669) | Cod sursa (job #2743787) | Cod sursa (job #2234016) | Cod sursa (job #2305745)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int main() {
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string s;
in >> s;
vector<char> v(s.size() * 2 + 1);
int ii = 0;
v[ii ++] = '$';
for(auto it : s) {
v[ii ++] = it;
v[ii ++] = '$';
}
vector<int> p(v.size(), 0);
int r = 0, pos = 0;
int ans = 0;
for(int i = 1; i < v.size(); i ++) {
if(r > i)
p[i] = min(r - i + 1, p[2 * pos - i]);
while(i - p[i] - 1 >= 0 && v[i + p[i] + 1] == v[i - p[i] - 1])
p[i] ++;
if(i + p[i] > r) {
r = i + p[i];
pos = i;
}
ans += ((p[i] + 1) / 2);
}
out << ans;
return 0;
}