https://codeforces.com/contest/1121/problem/F

题意：

要压缩字符串，必须将s表示为几个非空字符串的串联：s=t[1]t[2]…t[k]。

这些字符串的第i个应使用以下两种方式之一进行编码：

1. 如果|t[i]|=1，意味着当前字符串由单个字符组成， 可以对其进行编码，支付a个硬币；

2. 如果t[i]是t[1]t[2]…t[i-1]的子串， 可以对其进行编码，支付b个硬币。t[i]可以为单个字符，也可以是多个字符。

您的任务是计算压缩给定字符串s所需的最小硬币数量。

题解：

后缀自动机 + DP

逐个上传字符，动态构造后缀自动机树，同时搜索后面的t[i]是否为t[1]t[2]…t[i-1]的子串