算法标签

• 前缀压缩（Prefix Compression）
• 字符串匹配（String Matching）
• 贪心算法（Greedy Algorithm）

题意分析

题目要求实现一种前缀压缩算法，用于压缩字符串序列 $A_1, A_2, \dots, A_N$。压缩规则如下：

1. 公共前缀处理：
   • 若相邻字符串 $A_{i}$ 和 $A_{i+1}$ 有长度为 $j$ 的公共前缀，则 $A_{i+1}$ 压缩为 $[j] + A_{i+1}[j+1:]$，其中 $[j]$ 是一个单字符（编码为 $j$）。
2. 无公共前缀处理：
   • 若 $j=0$，则 $A_{i+1}$ 前添加一个零字节（长度 $+1$）。
3. 目标：计算压缩后的最小总长度。

约束条件：

• $1 \leq N \leq 10000$，$1 \leq \text{len}(A_i) \leq 255$。

解题思路

1. 公共前缀计算：

   • 对于相邻字符串 $A_i$ 和 $A_{i+1}$，计算其最长公共前缀长度 $j$。
   • 使用双指针法逐个字符比较，直到字符不匹配或到达任一字符串末尾。

2. 压缩长度计算：

   • 初始字符串 $A_1$ 直接存储，长度为 $\text{len}(A_1)$。
   • 后续每个字符串 $A_{i+1}$ 的压缩长度为 $1 + (\text{len}(A_{i+1}) - j)$，其中 $1$ 是前缀长度编码字符。

3. 总长度累加：

   • 总长度公式：$$\text{Total} = \text{len}(A_1) + \sum_{i=2}^N \left(1 + \text{len}(A_i) - \text{LCP}(A_{i-1}, A_i)\right) $$其中 $\text{LCP}$ 为最长公共前缀。

代码说明

1. 输入处理：

   • 使用二维字符数组 ve 存储所有字符串。
   • 第一字符串长度直接作为初始总长度。

2. 公共前缀计算：

   • 双指针 i 和 j 同步遍历相邻字符串的字符，统计匹配的公共前缀长度 js。

3. 压缩逻辑：

   • 总长度增加 $1 + (\text{当前字符串长度} - \text{公共前缀长度})$。
   • 若公共前缀为 $0$，则 $+1$ 对应零字节。

4. 输出结果：

   • 打印压缩后的总长度 jg。

参考代码

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio> 
using namespace std;
char ve[10004][260];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		scanf("%s",&ve[i]);
	}
	int jg=strlen(ve[0]);
	for(int k=1;k<n;k++)
	{
		int js=0;
		int il=strlen(ve[k]);
		int jl=strlen(ve[k-1]);
		for(int i=0,j=0;i<il&& j<jl;i++,j++)
		{
 
			if(ve[k][i]==ve[k-1][j])
			{
				js++;
			}else
			{
				break;
			}
		}
		jg=jg+1+strlen(ve[k])-js;//用一个字符表示数字 
	}
	printf("%d\n",jg);
	return 0;
}