Pagini recente » Cod sursa (job #3164582) | Cod sursa (job #2200885) | Cod sursa (job #2588584) | Cod sursa (job #497365) | Cod sursa (job #2305696)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int main() {
string s;
in >> s;
string v;
v = v + '$';
for(auto it : s) {
v = v + it;
v = v + '$';
}
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(r < i) {
int j = i - 1, k = i + 1;
p[i] = 1;
while(j >= 0 && k < v.size() && v[j] == v[k]) {
j --;
k ++;
p[i] ++;
}
} else {
int dif = i - pos;
if(p[pos - dif] + i - 1 < r) {
p[i] = p[pos - dif];
} else {
int j = i - p[pos - dif], k = i + p[pos - dif];
p[i] = p[pos - dif];
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);
}
out << ans;
return 0;
}