异世界的文章分割者 - 题目

因无意中惹恼了掌管天空的神祗，作为惩罚，艾德被流放到了异世界。与原来的世界相比，异世界的语言同样是用 $26$ 个小写英文字母来传达信息；但不同之处在于，其信息的表达并不依赖于断句。但如果一个句子包含的信息量过大，则会让人无法接受。具体来说，对于两个字符串 $s_1,s_2$，定义 $w(s_1,s_2)$ 为有多少个不同的字符串是 $s_1,s_2$ 的公共子串，那么对于一个长度为 $m$ 的句子 $t$，设 $t[l, r]$ 表示 $t$ 中第 $l$ 个字符到第 $r$ 个字符组成的字符串，下标从 $1$ 开始，则其包含的信息量为 $$ val(t) = \sum_{i=1}^{m-1} w^2(t[1,i],t[i+1,m]) $$ 好不容易适应异世界生活的艾德，凭借着自己以往的算法学习经历，应聘到了仅在异世界才有的职业——文章分割者。他每天的任务就是把文章分隔成一个个句子。为了保持美观，一篇文章中的句子数量必须恰好为 $k$。艾德要做的就是在满足上述条件下，使信息量最大的句子中包含的信息量尽可能少，以增强文章的可读性。

为了实现逃离异世界的计划，艾德需要去寻找散落在各地的时间碎片。但为了能够继续在异世界生存，他又不能丢掉这份工作，于是他找到了你来帮助他通过每天的任务检查。具体来说，你只需要对每篇文章回答，在使得信息量最大的句子中包含的信息量尽可能少的条件下，分割后所有句子中最大的信息量是多少。

输入格式

第一行包含两个整数 $n,k$，表示文章的长度以及需要划分出的句子数。

第二行包含一个长度为 $n$ 且仅由小写字母组成的文章 $t$。

输出格式

输出一行一个整数表示分割后句子中最大的信息量。

样例数据

样例 1 输入

10 3
ababababab

样例 1 输出

样例 2 输入

15 2
abcabcddcbacbad

样例 2 输出

子任务

对于所有数据，$1 \leq n \leq 5 \times 10^4, 1 \leq k \leq n$。保证答案不超过 $10^{18}$。

Subtask 1(10 pts): $n \leq 10$
Subtask 2(10 pts): $n \leq 50$
Subtask 3(20 pts): $n \leq 200$
Subtask 4(20 pts): $n \leq 1000$
Subtask 5(40 pts): No additional constraints.

QOJ.ac

QOJ

# 5368. 异世界的文章分割者