# O(sum of lengths of all words + |result|) solution

``````#define REP(i, n) for (int i = 0; i < (n); i++)

class Solution {
string a;
vector<int> z;
void manacher(int n) {
z.resize(n);
z[0] = 1;
for (int f, g = 1, i = 1; i < n; i++)
if (i < g && z[2*f-i] != g-i)
z[i] = min(z[2*f-i], g-i);
else {
g = max(g, f = i);
for (; g < n && 2*f-g >= 0 && a[2*f-g] == a[g]; g++);
z[f] = g-f;
}
}
public:
vector<vector<int>> palindromePairs(vector<string>& words) {
unordered_multimap<string, int> ls, rs;
REP(i, words.size()) {
string &w = words[i];
int n = w.size(), nn = 2*n+1;
a = string(nn, '.');
REP(j, n)
a[2*j+1] = w[j];
manacher(nn);
REP(j, nn) {
bool l = z[j] == j+1, r = j+z[j] == nn;
if (l)
ls.emplace(w.substr((j+z[j])/2), i);
if (r)
rs.emplace(w.substr(0, (j-z[j]+1)/2), i);
}
}
vector<vector<int>> ret;
REP(i, words.size()) {
string w = words[i], ww = w;
reverse(ww.begin(), ww.end());
auto its = ls.equal_range(ww);
for (auto it = its.first; it != its.second; ++it)
if (it->second != i)
ret.push_back(vector<int>{i, it->second});
its = rs.equal_range(ww);
for (auto it = its.first; it != its.second; ++it)
if (w.size() < words[it->second].size())
ret.push_back(vector<int>{it->second, i});
}
return ret;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.