哈工大软件安全实验：最长公共子序列算法实现

"1140320206-霍峻杰-实验三2" 在本实验报告中，哈尔滨工业大学计算机学院的学生霍峻杰探讨了软件安全领域的一个重要主题——恶意代码特征提取，特别是基于最长公共子序列（Longest Common Subsequence, LCS）的方法。实验的主要目标是理解和掌握如何从网络恶意代码中提取特征，以及如何通过动态规划算法实现最长公共子序列的提取。 首先，实验内容要求理解基于最长公共子序列的协议特征提取方法。最长公共子序列是指两个或多个序列中相同元素组成的最长序列，这些元素在各自的序列中保持原有的相对顺序。在恶意代码分析中，这种方法可以用于识别和比较不同样本中的相似性，从而发现潜在的威胁模式。 实验要求参与者准备ASCII字符集作为输入，不涉及多字节编码的中文或英文字符。程序需接受两个字符串作为输入，并输出它们的最长公共子序列。实验结果应包括算法流程图、算法说明、关键数据结构、实验结果以及程序源码。 算法流程基于动态规划的思想，通过构建一个二维数组L(m,n)，记录两个字符串在不同位置上的最长公共子序列的长度。当字符串末尾字符相同时，可以在前一个子问题的最长公共子序列后添加该字符；若不相同，则选择其前一个子问题中较长的公共子序列。 实验中关键的数据结构是动态规划的二维数组，用于存储回溯信息，以便在找到最长公共子序列的长度后，能通过回溯找出具体的序列。实验结果部分会展示算法的实际运行情况，包括输出的最长公共子序列。 提供的程序源码采用了Python语言，定义了一个名为LCS的类，包含了输入字符串的处理和计算最长公共子序列的函数。函数首先检查输入是否为字符串类型，接着初始化必要的数据结构，如动态规划数组和回溯方向列表，然后计算并返回最长公共子序列。 这个实验旨在通过实践操作，使学生深入理解最长公共子序列的概念，掌握其在恶意代码特征提取中的应用，以及如何运用动态规划解决此类问题。这不仅是对理论知识的巩固，也是对编程技能和问题解决能力的锻炼。