Pagini recente » Cod sursa (job #112896) | Cod sursa (job #2069277) | Cod sursa (job #264794) | Cod sursa (job #1381213) | Cod sursa (job #2791087)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int const NMAX = 1000000;
int n;
string input;
string s;
int dp[1 + 2 * NMAX + 1];
int main() {
fin >> input;
s.push_back('$');
for(int i = 0; i < input.length(); i++) {
s.push_back('*');
s.push_back(input[i]);
}
s.push_back('*');
s.push_back('#');
//cout << s << "\n";
n = s.length();
dp[0] = 0;
int c = 0;
int right = c;
//cout << 0 << " " << dp[0] << " " << c << " " << right << "\n";
for(int i = 1; i < n; i++) {
if(i < right) {
dp[i] = min(dp[2*c-i], right-i);
}
while(s[i-dp[i]-1] == s[i+dp[i]+1]) {
dp[i]++;
}
if(i + dp[i] > right) {
c = i;
right = i + dp[i];
}
//cout << i << " " << dp[i] << " " << c << " " << right << "\n";
}
int ans = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '$' || s[i] == '#' || s[i] == '*') {
ans += dp[i]/2;
} else {
ans += (dp[i]+1)/2;
}
//cout << (dp[i]+1)/2 << " ";
//ans += dp[i]/2;
}
fout << ans;
}