一个字符串问题的思考

一、问题描述：

求解给定文本text中以字符A开头，字符B结尾的子串数量。例如，文本ABCAAB中以A开头B结尾的子串分别为AB,ABCAAB,AAB,AB共4个。

二、问题分析及算法设计：

字符串问题求解的通用策略：我从《TCPL》中学到的印象最深的一点，就是"逐字符处理"策略（同时注意'\0'的处理）。

首先，使用蛮力法求解：设置两个下标i,j;i指向已搜索到的A的位置，j指向已搜索到的B的位置。算法描述如下：

STEP1：从字符串最左边开始扫描，首先用i遍历搜索A：若到达字符串末尾仍没有搜索到，则转至STEP3；

若搜索到A则停止，转至STEP2；

STEP2：初始化j为i的下一个位置并开始搜索B：若到达字符串末尾没有搜索到，则i移到下一个位置并转至STEP1；

若搜索到B，则子串数目次数加一，并继续向前搜索，直到字符串末尾并转至STEP1；

STEP3：搜索结束，退出算法。

这样的蛮力算法，其时间效率取决于A在字符串中出现的次数Na,T(n)=O(n*Na),n是字符串长度。也可以从右往左搜索，其时间效率为T(n)=O(n*Nb),Nb是B在字符串中出现的次数。如果知道A和B在文本中出现的次数，那么就可以选择从左往右或者从右往左的遍历方式。最差情况下，例如全A串，则效率为O(n*n).

有没有可能找到更好的算法呢？

我们知道，分治算法通常具有O(nlogn)的效率，那么，这个问题是否可以采用分治法来求解呢？答案是肯定的。

假设N[left:right]是文本text[left:right]中以A开始B结尾的子串数量，则整个文本中以A开始B结尾的子串数量为

N[0:n]=N[0:n/2]+N[n/2+1:n]+Na*Nb.Na是A在text[0:n/2]中出现的次数，Nb是B在text[n/2+1:n]中出现的次数；因为在后半段文本中的所有B都出现在前半段文本中的所有A之后(每个A与每个B都形成合乎要求的子串)，而在后半段文本中的所有A出现在前半段文本中的所有B之后（每个A与每个B都不能形成合乎要求的子串），所以，两半段文本合并时的子串数量应该是Na*Nb.这样，一个递归分治算法的模型基本就出来了，其时间复杂度为T(n)=2T(n/2)+O(n)=O(nlogn).

例子：N(ABCAAB)=N(ABC)+N(AAB)+1*1=4

N(ABC)=N(A)+N(BC)+1*1=1

N(AAB)=N(A)+N(AB)+1*1=2

N(BC)=N(B)+N(C)+0*0=0

N(AB)=N(A)+N(B)+1*1=1

因此，ABCAAB中以A开头B结尾的子串数量有4个。

能不能找到线性时间的算法呢？看上去似乎有可能，却又不是那么明显。在《编程珠玑I》的算法设计技术那一章里，作者采用四种算法(本质上是三种不同类型的算法)分别进行了设计，并在小结中提到：凡是数组问题，都可以考虑动态规划法来求解。那么，是否适用于本题呢？

假设给定文本中前n个字符组成的文本中以A开头B结尾的子串数量为Count[n],A出现的次数为Na,则前n+1个字符组成的文本中以A开头B结尾的子串数量为：

[1]若第n+1个字符不是结尾字符B，那么，Count[n+1]=Count[n];

[2]若第n+1个字符是结尾字符B，那么，Count[n+1]=Count[n]+Na.

这样，我们推导出了解的递推关系式。更进一步地，首先初始化子串数量count及开头字符出现次数beginNum为0；接着，从第一个字符开始，若该字符是开头字符，则beginNum++;若字符是结尾字符，则count+=beginNum;若该字符既不是结尾字符也不结束字符，那么，count,beginNum均不变；

注意，当开头字符和结尾字符相同时，上述算法会出现问题。此时，只要计算开头字符出现的次数Na,则子串数量应为Na*(Na-1)/2.

例子：ABCAAB

[1]count=0;Na=0;

[2]搜索到A：count=0;Na=1;

[3]搜索到B：count+=Na→count=1;Na=1;

[4]搜索到C：count=1;Na=1;

[5]搜索到A：count=1;Na=2;

[6]搜索到A：count=1;Na=3;

[7]搜索到B：count+=Na→count=4;Na=3;

因此，ABCAAB中以A开头B结尾的子串数量有4个。

三、完整程序：

/**substrNum.c:此程序计算给定文本中以给定字符开头和结尾的字串的数目*比如ABCAAB中，以A开头B结尾的子串有AB,ABCAAB,AAB,AB4个。*/#include#include#includeintsubstrnum(char*,char,char);intsubstrnumDIV(char*text,charbeginc,charendc);intsubstrnumDYN(char*text,charbeginc,charendc);intsubstrnumREC(char*text,intleftIndex,intrightIndex,charbeginc,charendc);voidtest(int(*fun)(char*,char,char));intmain(){printf("\n*******使用蛮力求解********\n");test(substrnum);printf("\n*******使用分治法求解*******\n");test(substrnumDIV);printf("\n********使用动态规划法求解*******\n");test(substrnumDYN);return0;}/**substrnum:在给定文本text中以字母beginc开头，字母endc结尾的子串*蛮力法求解：算法时间O(n*Na)Na,是开始字符在字符串中出现的次数。*或从右向左扫描，O(n*Nb),Nb是结尾字符在字符串中出现的次数*/intsubstrnum(char*text,charbeginc,charendc){assert(text!=NULL);inti=0,j;intcount=0;char*p=text;while(1){while(*(p+i)&&(*(p+i)!=beginc)){i++;}if(*(p+i)=='\0')break;j=i+1;while(*(p+j)){if(*(p+j)==endc){count++;}j++;}i++;}returncount;}/**substrnumDYN:在给定文本text中以字母beginc开头，字母endc结尾的子串*使用动态规划法求解：*若给定文本的前n个字符组成的字符串中所含子串数目为count[n],开始字符出现次数为beginNum;*则前n+1个字符串中所含子串数目为：*1.若第n+1个字符不是结尾字符，则count[n+1]=count[n];*2.若第n+1个字符是结尾字符，则count[n+1]=count[n]+beginNum**/intsubstrnumDYN(char*text,charbeginc,charendc){assert(text!=NULL);char*p=text;intcount=0;intbeginNum=0;while(*p){if(*p==beginc){//情况1：该字符是开始字符beginNum++;}elseif(*p==endc){//情况2:该字符是结尾字符count+=beginNum;}p++;//情况1：该字符既不是开始字符也不是结尾字符}if(beginc==endc){//开始字符与结尾字符相同returnbeginNum*(beginNum-1)/2;}returncount;}/**substrnumDIV:在给定文本text中以字母beginc开头，字母endc结尾的子串*使用分治法求解：*将给定文本分成两端text[0:n/2]和text[n/2+1:n-1],则子串数量为：*N(text)=N(text[0:n/2])+N(text[n/2+1:n-1])+NB*NE*其中，NB是开始字符在text[0:n/2]中出现的次数，NE是结尾字符在text[n/2:n-1]中出现的次数*算法时间：T(n)=2T(n/2)+n=O(nlogn)*/intsubstrnumDIV(char*text,charbeginc,charendc){assert(text!=NULL);returnsubstrnumREC(text,0,strlen(text)+1,beginc,endc);}intsubstrnumREC(char*text,intleftIndex,intrightIndex,charbeginc,charendc){if(rightIndex==leftIndex){return0;}else{intmid=(rightIndex-leftIndex+1)/2+leftIndex;char*p=text+leftIndex;char*q=text+mid;intnb=0;intne=0;while(*p&&p字符串问题的例子是为了说明什么呢？主要是因为，我认为它非常生动地演示了字符串问题的几种主要思路和算法：蛮力法、分治法、动态规划法。另外，还有一种算法，是对字符串进行预处理，比如高效字符串匹配KMP算法就是这么做的。

在这个问题中，可以首先遍历一次文本（时间是O(n)），分别将A，B出现的位置存储在两个数组中。仍以ABCAAB为例：首先可求得a[]:1,4,5;b[]:=2,6.接着，求a与b的笛卡尔乘积中(a,b)(a<b)的个数即可。可以在O(len(a)+len(b))的时间内求解，只是在遍历过程中有点技巧。因此，整个算法的时间复杂度是O(n).