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

題意：

要壓縮字符串，必須將s表示為幾個(gè)非空字符串的串聯(lián)：s=t[1]t[2]…t[k]。

這些字符串的第i個(gè)應(yīng)使用以下兩種方式之一進(jìn)行編碼：

1. 如果|t[i]|=1，意味著當(dāng)前字符串由單個(gè)字符組成， 可以對(duì)其進(jìn)行編碼，支付a個(gè)硬幣；

2. 如果t[i]是t[1]t[2]…t[i-1]的子串， 可以對(duì)其進(jìn)行編碼，支付b個(gè)硬幣。t[i]可以為單個(gè)字符，也可以是多個(gè)字符。

您的任務(wù)是計(jì)算壓縮給定字符串s所需的最小硬幣數(shù)量。

題解：

后綴自動(dòng)機(jī) + DP

逐個(gè)上傳字符，動(dòng)態(tài)構(gòu)造后綴自動(dòng)機(jī)樹，同時(shí)搜索后面的t[i]是否為t[1]t[2]…t[i-1]的子串