题解 CF710F 【String Set Queries】

唐一文 · 2021-10-17 23:16:56 · 题解

题目传送门

下文令 \text{len}=\sum|s|。

首先在查询时一个很暴力的思路就是枚举模板串的所有子串，并统计在集合中的出现次数，用哈希优化。复杂度 O(\text{len}^2)。

而优化这个暴力的方法很简单，只枚举集合中的字符串的长度作为子串的长度即可。复杂度 O(\text{len}\sqrt{\text{len}})。

因为在最坏情况下，集合中的字符串长度各不相同。当字符串最多时，长度一定是 1,2,3,... 一直到某个长度 t。而 1+2+\cdots+t\leq \text{len}，所以 t\leq \sqrt{2\text{len}}，最多只会有 \sqrt{2\text{len}} 个不同的长度。所以复杂度为 O(\text{len}\sqrt{\text{len}})。

注意此题卡自然溢出，但是没卡非自然溢出的单哈希（

Code