int n = (int)s.size();

if (n == 0)

return vector<int>();

vector<int> res(2 * n - 1, 0);

int l = -1, r = -1;

for (int z = 0; z < 2 * n - 1; z++) {

int i = (z + 1) >> 1;

int j = z >> 1;

int p = (i >= r ? 0 : min(r - i, res[2 * (l + r) - z]));

while (j + p + 1 < n && i - p - 1 >= 0) {

if (!(s[j + p + 1] == s[i - p - 1]))

break;

p++;

}

if (j + p > r) {

l = i - p;

r = j + p;

}

res[z] = p;

}

// Time Complexity: O(N), Space Complexity: O(N)

return res;

vector<int> res = manacher(txt);

int n = (int)txt.size();

vector<string> answer;

for (int z = 0; z < 2 * n - 1; ++z) {

int i = (z + 1) / 2;

int j = z / 2;

if (i > j && res[z] == 0)

continue;

int from = i - res[z];

int to = j + res[z];

string pal = "";

for (int i = from; i <= to; ++i)

pal.push_back(txt[i]);

answer.push_back(pal);

}

return answer;