1
class Solution {
2
 public:
3
  // Maybe I should learn trie! :'( this code just beats the time limit !
4
  pair<bool, bool> dp[5001][301];
5
  long long mod = 1011001110001111, base = 31;
6
  pair<long long, long long> Hashes[5001];
7
  vector<vector<int>> ans;
8
  vector<pair<long long, int>> pos[301];
9
  vector<pair<long long, int>> posR[301];
10
  vector<vector<int>> palindromePairs(vector<string> &words) {
11
    for (int i = 0; i < words.size(); i++) {
12
      long long hashL = 0, hashR = 0;
13
      long long pw = 1;
14
      for (int j = 0; j < words[i].size(); j++) {
15
        hashR = ((hashR * base) % mod + (words[i][j] - 'a' + 1)) % mod;
16
        hashL = (hashL + ((words[i][j] - 'a' + 1) * pw) % mod) % mod;
17
        dp[i][j].first = (hashL == hashR);
18
        posR[j + 1].push_back({hashL, i});
19
        pw = (pw * base) % mod;
20
      }
21
      Hashes[i] = {hashL, hashR};
22
      hashL = 0, hashR = 0, pw = 1;
23
      int l = 1;
24
      for (int j = words[i].size() - 1; j >= 0; j--) {
25
        hashR = ((hashR * base) % mod + (words[i][j] - 'a' + 1)) % mod;
26
        hashL = (hashL + ((words[i][j] - 'a' + 1) * pw) % mod) % mod;
27
        dp[i][j].second = (hashL == hashR);
28
        pos[l++].push_back({hashL, i});
29
        pw = (pw * base) % mod;
30
      }
31
    }
32
    set<pair<int, int>> ss;
33
    for (int i = 0; i < words.size(); i++) {
34
      int len = words[i].size();
35
      long long cur1 = Hashes[i].first;
36
      long long cur2 = Hashes[i].second;
37
      for (int k = 0; k < pos[len].size(); k++) {
38
        pair<long long, int> nxt = pos[len][k];
39
        if (nxt.first == cur1 && i != nxt.second) {
40
          int tot = words[nxt.second].size();
41
          int pref = (tot - len) - 1;
42
          if (pref >= 0 && dp[nxt.second][pref].first) {
43
            ss.insert({i, pos[len][k].second});
44
          } else if (pref < 0) {
45
            ss.insert({i, pos[len][k].second});
46
          }
47
        }
48
      }
49
      for (int k = 0; k < posR[len].size(); k++) {
50
        pair<long long, int> nxt = posR[len][k];
51
        if (nxt.first == cur2 && i != nxt.second) {
52
          if (len < words[nxt.second].size() && dp[nxt.second][len].second) {
53
            ss.insert({nxt.second, i});
54
          } else if (len >= words[nxt.second].size()) {
55
            ss.insert({nxt.second, i});
56
          }
57
        }
58
      }
59
    }
60

61
    // palindrome + "" empty is a valid pair
62
    for (int i = 0; i < words.size(); i++) {
63
      if (words[i].size() == 0) {
64
        for (int j = 0; j < words.size(); j++) {
65
          int len = words[j].size();
66
          if ((words[j].size() == 0 || dp[j][len - 1].first) && j != i) {
67
            ss.insert({i, j});
68
            ss.insert({j, i});
69
          }
70
        }
71
      }
72
    }
73
    for (pair<int, int> p : ss) ans.push_back({p.first, p.second});
74
    return ans;
75
  }
76
};