[题目总结] [COCI2015-2016#2] SAVEZ
题目让我们判断 \(s_i\) 是否是 \(s_j\) 的开头结尾。首先想到字符串哈希，这样仍然不优美，暴力判断点对是 \(O(n^2)\) 的。
如果这个时候卡住了，不妨往其他方面想想。看到前缀，我们自然地想到 Trie。那么这道题就做完一半了。
注意题目求的是子序列，那么这个子序列必定是相邻的两个字符串满足条件。这样想到一个朴素 DP：设 \(f_i\) 表示做到 \(i\) 的最长长度，那么如果 \(j>i\) 并且 \(s_i\) 与 \(s_j\) 满足条件，就可以 \(f_i\to f_j\) 。具体地，是：
\[f_j=\max{f_i+1} \]这样不好直接转移是 \(O(n^2)\) 的。回到开始的想法，我们为什么不在 Trie 上 DP 呢？回想一下一个字符串插入的过程，如果说我们在插入时，碰到一个 Trie 上的节点，是之前一个字符串的结尾，那么是不是可以字符串哈希 \(O(1)\) 判断这个节点对应的字符串是不是上述的 \(i\) 了？这样，我们再标记一下每个字符串结尾节点即可。
但是你会发现这道题只有 64MB，卡空间，直接 trie[N][26] 会 MLE，十分毒瘤。一般地，我们的 Trie 数组是 trie[N][26] 。但是啊，显然不会有 \(2\times 10^6\) 个节点。于是考虑优化，换成 trie[26][N] ，将它看成26个 unordered_map 即可。至此，这道题做完了。