Pagini recente » Cod sursa (job #1546219) | Cod sursa (job #1029181) | Cod sursa (job #1531647) | Cod sursa (job #2366049) | Cod sursa (job #2864969)
/*
__
_.--"" |
.----. _.-' |/\| |.--.
| |__.-' _________| |_) _______________
| .-""-.""""" ___, `----'")) __ .-""-.""""--._
'-' ,--. ` |Cezar| .---. |:.| ' ,--. ` _`.
( ( ) ) __| 7 |__\\|// _..-- \/ ( ( ) )--._".-.
. `--' ;\__________________..--------. `--' ;--------'
`-..-' `-..-'
*/
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
const int N = 1e6 + 5;
char s[2*N];
int dp[2*N];
void addSpaces(ifstream &in){
char s2[N];
in>>s2;
int l = strlen(s2);
for(int i = 0;i<l;i++){
s[i*2] = '#';
s[i*2+1] = s2[i];
}
s[l*2] = '#';
}
int main() {
ifstream in("pscpld.in");
ofstream out("pscpld.out");
addSpaces(in);
int l = strlen(s);
int oglinda = 0,dr = 0;
for(int i=0;i<l;i++){
// cout<<i<<' '<<oglinda<<' '<<dr<<'\n';
if(i<=dr)
dp[i] = min(dp[oglinda - (i - oglinda)], dr - i );
while(i - dp[i]-1>=0 && i+dp[i]+1<l && s[i - dp[i]-1] == s[i+dp[i]+1]){
dp[i]++;
}
if(i+dp[i]>dr) {
oglinda = i;
dr = i + dp[i];
}
}
/*
for(int i=0;i<l;i++)
out<<i<<' ';
out<<'\n';
for(int i=0;i<l;i++) {
out << s[i] << ' ';
if(i>9)
out<<' ';
}
out<<'\n';
*/
int rez = 0;
for(int i=0;i<l;i++) {
// out << dp[i] << ' ';
// if(i>9)
// out<<' ';
rez += dp[i]/2;
}
out<<rez + l/2;
return 0;
}