哈希 + 二分 + DP
首先看到题面,很容易想到一个$DP$,令$f[i]$为划分到$i$为止的方案数。
然后朴素的暴力转移是$O(n^2)$的,非常显然一个状态$i$能够转移到的$j$是一段连续的,进而想到使用前缀和优化。
对于这题,看到字符串匹配,第一反应想到字符串hash,同时看到$len \leq 8 $ ,考虑对于先给出的$n$个字符串,$O(len^2)$枚举它的子串,将其加入$map$中,但是要注意如果一个然后对于每个字符串,我们都统计一下它最后一次出现在哪里(于是就可以顺便判一下重)
然后我们在询问的时候,就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ
首先我作为一个蒟蒻,拿到字符串题,首先看看能不能无脑哈希
然后于是我们就发现了一个绝妙的做法:暴力枚举每个字符串能够转换成的字符串
于是我们就获得了$O(N * 8^4)$的优秀复杂度
显然会T飞QwQ
我们考虑再这个基础上进行优化