字符串对比是计算机科学的一个基本问题,在基因组比较、文本处理与压缩等实践中有着广泛应用。近几年,最小公共字符串划分(MCSP)问题得到越来越多算法与复杂性研究者的关注。MCSP问题要求将字符串A与B划分为公共子串,使划分后A中的每一段都与B中某一段相对应,且划分得到的公共子串数目最少。在基因组比较研究中,须将两个基因组分别看作字符串,计算两个字符串的最小公共字符串划分,从而建立两个基因组中基因的对应关系。要将字符串A和B划分为公共子串,A中每个字符出现的次数必须与B中此字符的出现次数相同。如果每个输入字符串中的字符最多出现k次,就称此问题为k-最小公共字符串划分MCSP问题。2-MCSP问题已经被证明是NP-hard,并且是APX-hard。目前最好的2-MCSP问题近似算法的近似度为1.1037,3-MCSP问题的近似度为4,k-MCSP问题近似度为(?)(k)。本文首先讨论以往MCSP问题研究结果,编程实现已有的贪心算法、Novel贪心算法、Educated贪心算法以及碰集算法,并进行测试实验。在此基础上,分析评测各个算法的优缺点。然后针对k-最小公共字符串划分问题,设计实现了一个新算法：定界贪心近似算法。定界贪心算法是在碰集算法的基础上改进而成,算法具有O(k)的算法近似度以及O(n)的时间复杂度。同时大量实验数据表明,定界贪心算法与碰集算法相比具有更好的计算性能。在实际测试实验中,未曾遇到定界贪心算法性能不如碰集算法性能好的实例。最后设计实现了MCSP问题的最优解算法与随机回溯算法。令m代表输入字符串中不同元素的个数,n代表字符串的长度,最优解算法可以在O((k!)mn)的时间内计算出k-最小公共字符串划分问题的一个或者所有最优解,对评估其他近似算法的实际运行效果有着重要作用。随机回溯算法具有很高的灵活性,既可以求出最优解,也可以根据实际要求在短时间内求出较好的解,两种算法都具有较高的实用价值。最后,对最小公共字符串划分问题进行了总结与展望。本文主要创新工作为：(1)设计实现了解答最小公共字符串划分问题的新近似算法,性能好于原有近似算法。(2)设计实现了解答最小公共字符串划分问题的最优解算法和随机回溯算法,对于最优解实际求解和近似算法评测具有重要价值。