Pagini recente » Cod sursa (job #2679568) | Cod sursa (job #3210632) | Cod sursa (job #2789800) | Cod sursa (job #1147803) | Cod sursa (job #3004931)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int N = 1000000;
int ans[N];
string str;
int manacher ( ) {
int mij = 0, dr = 0;
for ( int i = 1; i < str.size(); i++ ) {
ans[i] = 0;
if(i <= dr)
ans[i] = min ( ans[2 * mij - i], dr - i );
if(i + ans[i] >= dr) {
mij = i;
while(str[i + ans[i] + 1] == str[i - ans[i] - 1])
ans[i]++;
dr = i + ans[i];
}
}
return 0;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(0);
char chr;
str = "#*";
while(fin >> chr) {
str += chr;
str += '*';
}
str += '$';
manacher ();
long long int cnt = str.size() / 2 - 1;
for ( int i = 0; i < str.size(); i++ )
cnt += ans[i] / 2;
fout << cnt << '\n';
}