摘 要：串编辑一类字符串转换的问题，将两个字符串按照某种规则进行转换，转换将有三个消费函数，利用动态规划的方法可以得到各个操作的耗费之和，解决串编辑的问题。利用HASH 链式散列来实现LZW 压缩方法，利用字典组织，节省空间降低算法的复杂度，从而达到快速的代码简化法。
关键词：串编辑；LZW 压缩；动态规划；HASH
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2019）08-0094-03
String Editing and LZW Compression Algorithm Design
ZHAO Meiyong，SHI Haozhen，ZHU Zhenzhen
（Shandong University of Science and Technology，Jinan 250031，China）
Abstract：String editing a class of string conversion problem，the two strings are converted according to a certain rule，the conversion will have three consumption functions，using the dynamic programming method can get the sum of the cost of each operation，solve the problem of string editing. LASH compression method is implemented by HASH chain hashing，which uses dictionary organization to save space and reduce the complexity of the algorithm，thus achieving fast code simplification.
Keywords：string editing；LZW compression；dynamic programming；HASH
参考文献：
[1] Thomas H. Cormen，Charles E. Leiserson，Ronald L.Rivest，等. 算法导论 [M]. 第3 版. 殷建平，徐云，王刚，等，译. 北京：机械工业出版社，2012.
[2] Robert Sedgewick，Kevin Wayne. 算法 [M]. 第4 版. 谢路云，译. 北京：人民邮电出版社，2012.
[3] Brian W. Kernighan，Dennis M. Ritchie.C 程序设计语言 [M]. 徐宝文，李志，译. 北京：机械工业出版社，2004.
[4] 刘汝佳，陈锋. 算法竞赛入门经典：训练指南 [M]. 北京：清华大学出版社，2012.
[5] 刘汝佳. 算法竞赛入门经典 [M]. 第2 版. 北京：清华大学出版社，2014.
作者简介：
赵美勇（1997-），男，汉族，山东聊城人，本科，主要研究方向：计算机科学与技术；
史昊臻（1998-），女，汉族，山东菏泽人，本科，主要研究方向：通信工程；
朱珍珍（1998-），女，汉族，河南驻马店人，本科，主要研究方向：信息管理与信息系统。