前后缀字典树

lc3045

递到能到的 最远结尾

字典树o(n)

前后缀字典树pair

int p = (int) (s[i] - 'a') << 5 | (s[n - 1 - i] - 'a');

又抽象转化 包装为了前缀

o(L)

struct Node {
unordered_map<int, Node*> son;
int cnt = 0;
};

class Solution {
public:
long long countPrefixSuffixPairs(vector<string> &words) {
long long ans = 0;
Node *root = new Node();
for (string &s: words) {
int n = s.length();
auto cur = root;
for (int i = 0; i < n; i++) {
int p = (int) (s[i] - 'a') << 5 | (s[n - 1 - i] - 'a');
if (cur->son[p] == nullptr)
cur->son[p] = new Node();

cur = cur->son[p];
ans += cur->cnt; //边遍历 边统计 满足了天然的顺序性
}
cur->cnt++; //记录 满足某位置结尾的 数量
}
return ans;
}
};