[CF825F] String Compression 题解

本文主要是介绍[CF825F] String Compression 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给定一个字符串 $S$，其中出现循环的子串压缩后长度为：循环节出现次数十进制下的位数+循环节长度，无循环的串也需要压缩。求压缩后的最小长度。

思路

对于串 $T$，对其执行 KMP 算法后得到 $nxt$ 数组，可能的最小循环节长度 $len$ 即为 $|T|-nx{t}_{|T|}$，其中 $|T|$ 表示 $T$ 的长度；如果 $len\nmid |T|$ 则 $T$ 中无小的循环节（即循环节长度为 $|T|$）。对 $S$ 串进行压缩可以认为是把 $S$ 分成若干个子串，这些子串全部完全压缩。

考虑 dp。设 $f_i$ 表示将 $S$ 串的前 $i$ 个字符进行压缩的最小长度。初始 $f_i=i+1$。转移方程即为： f i ← min ⁡ { f j + c n t j + 1 , i } ( 1 ≤ j < i ≤ ∣ S ∣ ) f_i\gets\min\{f_j+cnt_{j+1,i}\}\ (1\le j<i\le |S|) fi​←min{fj​+cntj+1,i​} (1≤j<i≤∣S∣)，其中 $cn{t}_{x,y}$ 表示将 $S$ 中 $[x,y]$ 这个部分完全压缩后的长度，求法即为：对于每个 $1\le i\le |S|$，都将 $S$ 的前 $i-1$ 个字符删除后跑 KMP，求得的 $(j-i+1)-nx{t}_j(i\le j\le |S|)$ 即为 $cn{t}_i,j$，注意判断是否能够整除。时间复杂度 $O(n^2)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 8005;
char S[maxn]; int f[maxn],nxt[maxn];
int count(int x) { // 数出循环节十进制位数int res = 0;while (x) res ++, x /= 10;return res;
}
int n;
void KMP(char S[]) { // 求出的 nxt 数组下标从起点开始int len = strlen(S + 1);memset(nxt,0,sizeof(nxt)); for (int i = 2,now = 0;i <= len;i ++) {while (now && S[i] != S[now + 1]) now = nxt[now];if (S[i] == S[now + 1]) now ++;nxt[i] = now;}
}
int main() {scanf("%s",S + 1); n = strlen(S + 1);for (int i = 1;i <= n;i ++)f[i] = i + 1;for (int i = 0;i <= n;i ++) {KMP(S + i); // 以每个 i 为开头跑出 nxt 数组for (int len = 1;i + len <= n;len ++) { // 枚举完全压缩的区间长度int j = i + len;if (len % (len - nxt[len]) == 0) // 存在循环节f[j] = min(f[j],f[i] + count(len / (len - nxt[len])) + len - nxt[len]);else f[j] = min(f[j],f[i] + len + 1); // 否则只能整个压缩}}printf("%d",f[n]);return 0;
}

这篇关于[CF825F] String Compression 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---