<字符串移位包含问题>和<字符串相似度问题>

字符串处理的问题无论是做ACM题，还是实际项目开发中都是经常遇到的问题，字符串处理问题往往用到很多有意思的经典算法，个人觉得，对字符串的处理技巧能看出一个将要毕业的大学生的编码能力、算法基础和遇到问题的思考能力。最近就遇到两个字符串处理的问题：（1）字符串移位包含问题（2）计算字符串相似度的问题。

1.字符串的移位包含问题

问题定义：给定两个字符串str1和str2，所谓的移位包含就是说如果str2属于str1经过移位得到的新串的子串，则说str1移位包含str2，那么什么是str1移位得到的新串呢？比如ABCD经过移位1位可以得到的新串是BCDA，这种移位方式实际上是循环左移。这时如果str2 = “DA”，那么就可以说str1移位包含str2.

分析问题：我们可以枚举str1经过循环移位得到的新串str_tmp，然后如果str2是str_tmp的子串那么就满足了移位包含的问题了，但是这种思路效率并不高，整个算法的时间复杂度包括：循环移位的时间复杂度和判断是不是子串的复杂度（循环移位算法可以参见：数组循环移位中的学问数组循环移位中的学问）。这显然不是我们要的解题思路了，实际上无论字符串循环移位几位，最终得到的新串str_tmp都是经过两个str1连接得到的，比如ABCD经过循环移位可以得到：BCDA、CDAB、DABC、ABCD，实际上这四个经str1循环移位得到的新串都是str1str1 = “ABCDABCD”的子串。这时，您明白了吧，我们就可以省掉循环移位的复杂度了，使得整个算法的时间复杂度提高。

现在我们可以着重考虑判断str2是否是str1str1的子串的算法了，实际上在头文件<string.h>已经提供了strstr（str1，str2）函数，用来完成我们需要的功能，但是strstr函数的内部代码是这样的：

View Code

 1 char *strstr( const char *s1, const char *s2 ) 　　
 2 { 　　
 3     if ( !(len2 = strlen(s2)) ) 　　
 4         return (char *)s1; 　　
 5     for(;*s1;++s1) 　　
 6     { 　　
 7         if ( *s1 == *s2 && strncmp(s1,s2,len2)==0 ) 　　
 8             return (char *)s1; 　　
 9     } 　　
10     return NULL; 　　
11 }

可以看出来，这个函数采用的判断方法效率并不高，如果要进行大量的这种str2是不是str1str1的子串的判断或者str1和str2的长度比较长，则用这个算法就不是很好了，我们就要想别的算法了，实际上很自然就能想到快速模式匹配算法（KMP）了，这是基本每个数据结构的书都基本会介绍的算法，具体可以参考刘大有《数据结构》第2版，或者本人的另一篇随笔：快速模式匹配算法（KMP）。相信通过这些资料，把完整的代码写出来应该不是什么问题了，我这里就不写了。

但是可能大家会发现str1str1接在一起要花费O（N）的辅助空间啊，N是str1的长度，这个实际上是存在的，但是我们可以不是真正意义上的合并，这只是一种思想，实际操作的时候，比如要访问str1str1[N+3]，我们可以让其实际访问的是str1[3]来完成啊，这样就不需要多增加O（N）的辅助空间了。

2.计算字符串的相似度

问题定义：现存在两个字符串str1和str2，要想把这两个字符变得相同，可以有下面的操作：1.修改一个字符 2.增加一个字符 3.删除一个字符。比如：str1 = abc和str2 = ab，就可以通过增加或者删除一个c使得这两个字符变得相同；还比如str1 = abc，str2 = abd，这时需要修改c -> d或者修改d->c都可以使得两个字符串变得相同。可以看出这两个简单的例子，所需要的操作都是1，不妨称之为距离是1，实际上这里所说的相似度 = 距离+ 1 的倒数。那么如何计算给定的两个字符串的相似度呢？

分析问题：实际上str1和str2比较若首字母相同，则只需要比较str1[1~len1-1] 和 str2[1~len2-1]，不影响距离的变化。若str1和str2的首字母并不相同，那么我们科进行下面的6种操作的一种：

1.删除str1的第一个字符，然后继续计算str1[1~len1-1]和str2[0~len2-1] 之间的距离。

2.删除str2的第一个字符，然后继续计算str1[0~len1-1]和str2[1~len2-1]之间的距离。

3.修改str1的第一个字符等于str2的第一个字符，然后继续计算str1[1~len1-1]和str2[1~len2-1] 之间的距离。

4.修改str2的第一个字符等于str1的第一个字符，然后继续计算str1[1~len1-1]和str2[1~len2-1] 之间的距离。

5.在str1最前面增加一个字符使其等于str2的第一个字符，然后继续计算str1[0~len1-1]和str2[1~len2-1]之间的距离。

6.在str2最前面增加一个字符使其等于str1的第一个字符，然后继续计算str1[1~len1-1]和str2[0~len2-1] 之间的距离。

我们发现，无论是上述的哪一种变动方式，最后需要继续计算的情况只有三种：（1）计算str1[1~len1-1]和str2[1~len2-1] 之间的距离d1 （2）计算str1[1~len1-1]和str2[0~len2-1] 之间的距离d2 （3）计算str1[0~len1-1]和str2[1~len2-1]之间的距离d3，并且str1[0~len1-1]和str2[0~len2-1]之间的距离等于min（d1，d2，d3）+ 1，加1是因为做了一次操作。很显然了，这是一个递归程序：

代码：

CalStringDistance

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int MinValue(int d1,int d2,int d3)
 6 {
 7     int min = d1;
 8     if(d2 < min)
 9     {
10         min = d1;
11     }
12     if(d3 < min)
13     {
14         min = d3;
15     }
16     return min;
17 }
18 
19 int CalStringDistance(string strA,int pABegin,int pAEnd,string strB,int pBBegin,int pBEnd)
20 {
21     if(pABegin > pAEnd)
22     {
23         if(pBBegin > pBEnd)
24         {
25             return 0;
26         }
27         else
28         {
29             return pBEnd - pBBegin + 1;
30         }
31     }
32     if(pBBegin > pBEnd)
33     {
34         if(pABegin > pAEnd)
35         {
36             return 0;
37         }
38         else
39         {
40             return pAEnd - pABegin + 1;
41         }
42     }
43     if(strA[pABegin] == strB[pBBegin])//当前的字母相同，距离不必+1
44     {
45         return CalStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);
46     }
47     else
48     {
49         //d1,d2,d3保存可能三种递归情况所得到的距离
50         int d1 = CalStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin,pBEnd);
51         int d2 = CalStringDistance(strA,pABegin,pAEnd,strB,pBBegin+1,pBEnd);
52         int d3 = CalStringDistance(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);
53         return MinValue(d1,d2,d3)+1;
54     }
55 }
56 
57 int main()
58 {
59     string strA = "abe";
60     string strB = "abcd";
61     cout<<CalStringDistance(strA,0,2,strB,0,2)<<endl;
62     return 0;
63 }
64

总结：实际上在递归的过程中进行了大量的重复计算，比如我们要进行CalStringDistance(strA,1,2strB,1,2)，这时就会递归调用函数CalStringDistance(strA,1,2,strB,2,2)和CalStringDistance(strA,2,2,strB,2,2)，那么在执行CalStringDistance(strA,1,2,strB,2,2)的时候也难免调用CalStringDistance(strA,2,2,strB,2,2)，并且随着strA和strB的长度增加，这种重复会很多，也因此导致算法时间复杂度不高。那么如何避免这种重复计算呢？？

1.可以利用备忘录的思想，我们通过二维数组int flag[][]记录当前CalStringDistance(strA,pABegin,pAEnd,strB,pBBegin,pBEnd)的是否调用过，首先将数组初始化为-1，当第一次调用函数CalStringDistance(string strA,2,2,strB,2,2)的时候，将flag[2][2]赋值为函数的计算，前一个代表pABegin，后一个2代表pBBegin。这样下次调用CalStringDistance(string strA,2,2,strB,2,2)的时候发现flag[2][2]并不等于-1，就知道CalStringDistance(string strA,2,2,strB,2,2)已经计算过了，可以直接从flag[2][2]获得函数的结果。修改后的代码和原来的代码大同小异！！可是大家也发现了，这种方式多引入了O(len1*len2)的空间复杂度，不过随着strA和strB的长度增加，如果不这样做一定会大大影响效率的，是一定。

2. 也可以用递推的方法，既然已经知道了递推关系式，使用递推应该是能解决问题的，首先初始化cal[2][2]，cal[1][2]，cal[2][1]，cal这个二维数组的下标也和pABegin和pBBegin对应，然后计算CalStringDistance(string strA,1,2,strB,1,2)，实际上计算cal[1][1]，我们就可以利用cal[2][2]，cal[1][2]，cal[2][1]得到了，这样不断递推，就能得到最终结果，这种方式避免递归程序先天的劣势。

实际上上面的两种方法是完成动态规划的典型思路。动态规划真实太伟大啦，值得学习！！！

如果您觉得文章内容对您有用，不妨动一下手中的鼠标，轻击一下右下角的“推荐”，您的鼓励是我前进的动力~~~~

如果您觉得文章内容存在问题，不妨在评论中直言不讳，好的文章也需要热心而聪明的读者的参与~~~~