首先将所有字符串拼在一起做后缀数组。
我们需要求出每个后缀有多少个前缀满足条件(记为 fi)。
对于每个后缀,预处理出往后扩展到哪里会满足条件。对于这样的一段区间,公共前缀就是height的最小值(记为 x )。
一个区间 (l,r,x) 对 f 有以下影响:
- 对于 l≤i≤r,fi←max。
- 对于 i>r,f_i \leftarrow \max(f_i,\max(h_l \cdots h_i))
对于(1)维护一个单调队列,对于(2)直接记录 l 的最大值即可。
时间复杂度 O(N\log N)