int n = str.size(); vector<int> d(n + 1, 1); int l = 1, r = 1; int mx = 0; int p = 0; for (int i = 2; i < str.size(); i++) { if (i <= r) { d[i] = min(d[l + r - i], r - i + 1); } while (str[i + d[i]] == str[i - d[i]]) { d[i]++; } if (d[i] > mx) { mx = d[i]; p = i; } if (i + d[i] - 1 > r) { r = i + d[i] - 1; l = i - d[i] + 1; } } string ans = ""; // #a#b#b#a# for (int i = p - mx + 1; mx - 1 >= 1; i++) { if (str[i] != '#') { mx--; ans += str[i]; } } return ans; } };