Manchers algorithm

vector<vector<int> > d;  // d1 contains all palindromes of odd length with centre at i and d2 contains palindromes of even  length with right centre at i

void mancher(string s){
    int n = sz(s);
    d.resize(n,vector<int>(2));
    for (int t = 0; t < 2; t++) {
        int l = 0, r = -1, j;
        for (int i = 0; i < n; i++) {
            j = (i > r ) ? 1 : min(d[l+r-i+t][t],r-i+t) + 1;
        	while (i + j - t < n && i - j >= 0 && w[i + j - t] == w[i - j]) j++;
        	j--;
        	d[i][t] = j;
        	if (i + j + t > r) { l = i - j; r = i + j - t; }
        }
    }
}