Pagini recente » Cod sursa (job #169923) | Cod sursa (job #2774054) | Cod sursa (job #1869971) | Cod sursa (job #1127296) | Cod sursa (job #2305729)
#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;
p[0] = 1;
int ans = 0;
for(int i = 1; i < v.size(); i ++) {
if(i > r)
p[i] = 1;
else {
int dif = i - pos;
p[i] = min(r - i + 1, p[pos - dif]);
}
int j = i - p[i], k = i + p[i];
while(j >= 0 && k < v.size() && v[j] == v[k]) {
j --;
k ++;
p[i] ++;
}
if(i + p[i] - 1 > r) {
r = i + p[i] - 1;
pos = i;
}
ans += (p[i] / 2);
//cout << v[i] << " " << i << " " << p[i] << endl;
}
out << ans;
return 0;
}