刷题笔记合集🔗

TLV解析 Ⅱ

问题描述

两端通过TLV格式的报文来通信，现在收到小柯的一个TLV格式的消息包，要求生成匹配后的(tag, length, valueOffset)列表。

具体要求如下:

（1）消息包中多组tag、length、value紧密排列，其中tag,length各占1字节(uint8_t) , value所占字节数等于length的值

（2）结果数组中tag值已知，需要填充每个tag对应数据的length和valueOffset值(valueOffset为value在原消息包中的起始偏移量（从0开始，以字节为单位))，

即将消息包中的tag与结果数组中的tag进行匹配（可能存在匹配失败的情况，若结果数组中的tag在消息包中找不到，则length和valueOffset都为0)

（3）消息包和结果数组中的tag值都按升序排列，且不重复

（4）此消息包未被篡改，但尾部可能不完整，不完整的一组TLV请丢弃掉

输入格式

第一行: 一个字符串，代表收到的消息包。字符串长度在10000以内。

• 说明1: 字符串使用十六进制文本格式（字母为大写）来展示消息包的数据，如0F04ABABABAB代表一组TLV:前两个字符(0F）代表tag值为15，接下来两个字符（04）代表length值为4字节，接下来8个字符即为4字节的value。
• 说明2: 输入字符串中，每一组TLV紧密排列，中间无空格等分隔符

第二行: 需要匹配的tag数量 () 。

后面 行: 需要匹配的 个tag值（十进制表示)，递增排列。

输出格式

和需要匹配的 个tag对应的 行匹配结果，每一行由长度和偏移量组成。

样例输入

0F04ABABABAB
1
15

0F04ABABABAB1001FF
2
15
17

样例输出

4 2

4 2
0 0

数据范围

• 
• 字符串长度在10000以内

题解

这道题目要求解析TLV（Tag-Length-Value）格式的数据，并进行匹配查找。TLV是一种常见的数据编码方式，尤其在网络通信中广泛使用。

首先，需要理解TLV格式的构成：

• Tag: 标签，占1字节，表示这组数据的类型
• Length: 长度，占1字节，表示Value部分占用的字节数
• Value: 具体数据，长度可变，由Length指定

在这个题目中，需要注意几个关键点：

1. 输入字符串是十六进制文本格式，每两个字符代表一个字节
2. 每个Tag和Length各占1字节，即2个十六进制字符
3. Value的长度由Length指定，以字节为单位
4. valueOffset是指Value在原始消息包中的起始字节偏移量
5. 可能有不完整的TLV，需要丢弃

解题思路：

1. 遍历输入的十六进制字符串，每次取2个字符作为tag，接着的2个字符作为length
2. 计算value的长度（字节数），即length值，并计算对应的十六进制字符数（length值 * 2）
3. 计算当前value的起始偏移量（字节单位）
4. 检查是否有足够的字符来表示完整的value，如果没有则说明是不完整的TLV，丢弃
5. 将解析到的有效tag及其对应的length和valueOffset存储起来
6. 最后，遍历需要匹配的tag列表，输出对应的length和valueOffset（如果没有匹配到，则输出"0 0"）

具体实现时有一个重要细节：

• 在遍历字符串时，索引i的增加方式。首先处理完tag和length后，i需要跳过当前整个TLV块，然后才进入下一个TLV块的处理

时间复杂度：O(L + n)，其中L是输入字符串的长度，n是需要匹配的tag数量。 空间复杂度：O(t)，其中t是不同tag的数量。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
msg = input()
n = int(input())
tags = [int(input()) for _ in range(n)]

# 解析TLV消息
def parse_tlv(msg):
    # 存储tag与其对应的length和valueOffset
    tag_info = {}
    
    # 遍历消息字符串，每次解析一个TLV块
    i = 0
    while i + 4 <= len(msg):  # 确保至少能读到tag和length
        # 解析tag和length
        tag = int(msg[i:i+2], 16)
        length = int(msg[i+2:i+4], 16)
        
        # 计算valueOffset（字节为单位）
        value_offset = (i + 4) // 2
        
        # 计算value结束位置（字符索引）
        end_pos = i + 4 + length * 2
        
        # 检查是否有完整的value
        if end_pos > len(msg):
            # 不完整的TLV，丢弃
            break
        
        # 存储tag信息
        tag_info[tag] = (length, value_offset)
        
        # 移动到下一个TLV块
        i = end_pos
    
    return tag_info