【题解】UVA11922 String Factoring - Harvey

题意

给定字符串 \(S\)，若 \(S\) 的字串 \(T\) 是由循环节 \(X\) 循环而成，则可以将 \(T\) 缩短成 \(X\)，求最后 \(S\) 的最小长度。
数据范围：\(|S| \leq 80\)，多组测试样例。

解法

由于 \(|S|\) 很小，可以考虑区间动态规划。
设 \(f_{l,r}\) 表示 \([l,r]\) 区间缩短后的最小长度。
考虑转移：

1. 枚举中间分隔点 \(k\)，\(f_{l,r}=\min_{l\leq k <r} f_{l,k}+f_{k+1,r}\)。
2. 求 \([l,r]\) 的循环节，可以用 \(KMP\) 求出最长 \(border\)，记为 \(p\)，然后判断是否有 \((n-p)|n\)，如果不整除，那么没有循环节，否则循环节 \(|X| = n-p\)，将 \(|X|\) 记为 \(tt\)，于是有 \(f_{l,r} = f_{l,l+tt-1}\)。

时间复杂度为 \(\mathcal{O(Tn^3)}\)，\(T\)表示测试数量。