Pagini recente » Cod sursa (job #1421186) | Cod sursa (job #3364289) | Cod sursa (job #3364228) | Cod sursa (job #3363464) | Cod sursa (job #3364287)
#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, st = 0, dr = -1; i < tt.size() - 1; i++){
if(i <= dr) pal[i] = max(0, min(pal[st + dr - i], dr - i + 1));
for(; tt[i - pal[i]] == tt[i + pal[i]]; pal[i]++);
if(i + pal[i] - 1 > dr){
st = i - pal[i] + 1;
dr = i + pal[i] - 1;
}
}
int64_t ways = 0;
for(int i = 1; i < tt.size() - 1; i++){
ways += (pal[i] / 2);
}
out<<ways<<"\n";
return 0;
}