Pagini recente » Cod sursa (job #3364296) | Cod sursa (job #3364280) | Cod sursa (job #3364286) | Cod sursa (job #3364261) | Cod sursa (job #3364282)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int nmax = 1e6;
int n, pal[2 * nmax + 2]; string ss, tt;
int main(){
in>>ss;
tt = '$#';
for(int i = 0; i < ss.size(); i++){
tt += ss[i]; tt += '#';
}
tt += '&'; /// bounded with different characters
/// manacher's algorithm ///
for(int i = 1; i < tt.size() - 1; i++){
for(; tt[i - pal[i]] == tt[i + pal[i]]; pal[i]++);
}
int64_t ways = 0;
for(int i = 1; i < tt.size() - 1; i++){
ways += (pal[i] / 2);
}
out<<ways<<"\n";
return 0;
}