不会 PAM，来个简单做法。

考虑插入 $\$$ 字符，然后 manachar 找出所有回文子串。

考虑将所有回文子串截一半出来挂 Trie 上，显然点数是 $O(n)$ 的，数目统计可以树上差分。

注意到 manachar 的过程要求我们快速找到树上若干级祖先，又由于树是动态建立的，可以直接树上倍增找祖先。

总复杂度 $O(n\log n)$，空间复杂度 $O(n\log n+n|\Sigma|)$。

参考代码。