CF1393E2(字符串)

题目大意

有一些字典序不降的有序字符串，某大师给其中的一些字符串中加了恰好一个字符，你现在知道操作后的字符串数组，求原始字符串有多少种，(mod 10^9+7)

数据范围

(1 le n le 10^5,sum|S| le 10^6)

解题思路

首先是一个显然的 dp，(dp[x][y]) 表示第 x 串扔掉第 y 个字符且前 x 个串合法的方案数

从前一个串的某个位置转移来，只需要求消掉字符以后字典序满足不降即可

暴力做 + hash 二分判字典序大小是 (Theta(L^2log L)) 的

如果我们把所有串都排序，比较时用 hash二分时间复杂度是 (Theta(Llog^2L)) 的，显然出题人卡了这个做法

由于比较的是相邻两个串的字典序大小，如果求出来一个串内部的顺序，在归并排序一下就行了，因此我们考虑如何求出一个串去掉其中一个字符的字典序

考虑所有字符都不相同的情况，对于 (i,j(i <j)) 的字典序，我们比较 (s[i],s[i+1]) 的大小即可，那么如果字符有相同的情况呢，那么也很简单，我们找到最近的不相同的字符来比较即可，由于他们之间还满足这样一种性质若 (rk[i] <rk[j] (i le j)) 那么 (rk[i] < rk[k](j le k)) ，最后再把整串加到删掉最后一个字符后面即可

时间复杂度 (Theta(Llog L))

代码（还没有）