HBC236454[TJOI2013]攻击装置,图匹配Just Another String Problem题解 （每日一词：string）

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

You are given a stringsssof lengthnnnconsisting of lowercase English letters and a non-decreasing array{v1,v2,,vn}{v_1,v_2,cdots,v_n}{v1,v2,,vn}. A setTTTof non-empty strings is called good if an

You are given a string sss of length nnn consisting of lowercase English letters and a non-decreasing array {v1,v2,⋯ ,vn}{v_1,v_2,cdots,v_n}{v1​,v2​,⋯,vn​}. A set TTT of non-empty strings is called good if and only if: There does not exist a pair of strings in TTT such that one is a suffix of the other. Here, string AAA is said to be a suffix of string BBB if AAA can be obtained by deleting some letters (possibly, none) in BBB in the beginning. For a good set TTT, denote the value of TTT as ∑t∈Tv∣t∣sum_{tin T}v_{|t|}∑t∈T​v∣t∣​, where ∣t∣|t|∣t∣ is the length of string ttt. For a string ttt and some positive integer kkk, define f(t,k)f(t,k)f(t,k) as the maximum value among all good sets TTT that satisfies the following conditions: ∣T∣≤k|T|leq k∣T∣≤k; TTT only contains substrings of ttt. Here, string AAA is said to be a substring of string BBB if AAA can be obtained by deleting some letters (possibly, none) in BBB in the beginning and some letters (again, possibly none) in the end. You need to answer qqq queries. For each of them, you are given two values l,kl,kl,k (1≤l≤n,1≤k≤1091le lle n,1le kle 10^91≤l≤n,1≤k≤109), and you need to find out f(s[1,l],k)f(s[1,l],k)f(s[1,l],k), where s[1,l]s[1,l]s[1,l] denotes the prefix with lll letters of sss.

标签： HBC236454[TJOI2013]攻击装置 图匹配Just Another String Problem题解