palindromes

// дана строка s и её длина n
int d[1000001];

l = 0;
r = 0;
for(int i = 0; i < n; i++){
    if(i<=r){
        d[i] = min(d[l+r-i],r-i+1);
    }
    while(i - d[i] >= 0 &&
          i + d[i] < n &&
          s[i - d[i]] == s[i + d[i]]){
        d[i]++;
    }
    if(r < i + d[i] - 1){
        l = i - d[i] + 1;
        r = i + d[i] - 1;
    }
}