C实现求解给定文本中以指定字符开头和结尾的子串数量的三种算法

难度： ★

一、 问题描述：

求解给定

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

AB 共4个。

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

字符串问题求解的通用策略： 印象最深的一点，就是“逐字符处理”策略(同时注意 "\0"的处理)。

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

STEP1：

初始化 i = 0 , j = 0. 从字符串最左边开始。

STEP2：

用下标 i 遍历搜索A，若搜索到A，则记下 i 的位置并转至STEP2; 若到达字符串末尾仍没有搜索到，则转至 STEP4;

STEP3：

初始化 j 为 i 的下一个位置并开始搜索B： 若到达字符串末尾没有搜索到，则 i 移到下一个位置并转至STEP1;若搜索到B，则子串数目次数加一，并继续向前搜索，直到字符串末尾并转至STEP1;

STEP4：

搜索结束，退出算法。

例子： ABCAAB

第一趟： A: i = 0, B: j = 1, 5 num = 2;

第二趟： A: i = 3, B: j = 5 num = 1;

第三趟： A: i = 4, B: j = 5 num = 1

共计： 2 + 1 + 1 = 4.

这样的蛮力算法，其时间效率取决于A在字符串中出现的次数Na, T(n) = O(n * Na), n 是字符串长度。 也可以从右往左搜索， 其时间效率为 T(n) = O(n * Nb), Nb是 B 在字符串中出现的次数。

如果知道A和B在文本中出现的次数，那么就可以选择从左往右或者从右往左的遍历方式。最差情况下，例如全A串，则效率为O(n*n).

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

我们知道，分治算法通常能达到 O(nlogn)的效率，只要合并部分的时间能达到O(n) 。 那么，这个问题是否可以采用分治法来求解呢? 答案是肯定的。

假设 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出现在前半段文本中的所有

A出现在前半段文本中的所有B之后(每个A与每个B都不能形成合乎要求的子串)；

所以， 两半段文本合并时的子串数量应该是Na * Nb.这样，一个递归分治算法的模型基本就出来了，其时间复杂度为 T(n) = 2T(n/2) + O(n) = O(nlogn). 合并部分要求分别遍历字符串的两半段，时间为O(n).

例子： 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, AB 4个。

*/

#include

<stdio.h>

#include

<

string

.h>

#include

<assert.h>

int

substrnum(

char

*,

char

,

char

);

int

substrnumDIV(

char

* text,

char

beginc,

char

endc);

int

substrnumDYN(

char

* text,

char

beginc,

char

endc);

int

substrnumREC(

char

* text,

int

leftIndex,

int

rightIndex,

char

beginc,

char

endc);

void

test(

int

(*fun)(

char

*,

char

,

char

));

int

main(){   printf(

"

\n ******* 使用蛮力求解 ******** \n

"

);   test(substrnum);   printf(

"

\n ******* 使用分治法求解 ******* \n

"

);   test(substrnumDIV);   printf(

"

\n ******** 使用动态规划法求解 ******* \n

"

);   test(substrnumDYN);  

return

0

;}

/*

* substrnum: 在给定文本 text 中以字母 beginc 开头， 字母 endc 结尾的子串 * 蛮力法求解： 算法时间 O(n*Na) Na, 是开始字符在字符串中出现的次数。 * 或 从右向左扫描， O(n*Nb), Nb 是结尾字符在字符串中出现的次数

*/

int

substrnum(

char

*text,

char

beginc,

char

endc){   assert(text

!=

NULL);  

  int

i =

0

, j;

 

int

count =

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

++

;   }

 

return

count;}

/*

* 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 *

*/

int

substrnumDYN(

char

*text,

char

beginc,

char

endc){   assert(text

!=

NULL);

 

char

*p =

text;

 

int

count =

0

;  

int

beginNum =

0

;    

while

(*

p) {

     

if

(*p == beginc) {

//

情况 1： 该字符是开始字符

beginNum++

;      }        

else

if

(*p == endc) {

//

情况 2 : 该字符是结尾字符

count +=

beginNum;      }      p

++;

//

情况 1： 该字符既不是开始字符也不是结尾字符

  }

 

if

(beginc == endc) {

//

开始字符与结尾字符相同

return

beginNum * (beginNum -

1

) /

2

;   }

 

return

count;}

/*

* 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)

*/

int

substrnumDIV(

char

* text,

char

beginc,

char

endc){   assert(text

!=

NULL);

 

return

substrnumREC(text,

0

, strlen(text)+

1

, beginc, endc);}

int

substrnumREC(

char

* text,

int

leftIndex,

int

rightIndex,

char

beginc,

char

endc){

 

if

(rightIndex ==

leftIndex) {      

return

0

;   }

 

else

{

     

int

mid = (rightIndex - leftIndex +

1

) /

2

+

leftIndex;

     

char

*p = text +

leftIndex;

     

char

*q = text +

mid;

     

int

nb =

0

;

     

int

ne =

0

;

     

while

(*p && p < text+

mid) {

       

if

(*p ==

beginc) {             nb

++

;         }         p

++

;      }

     

while

(*q && q <= text+

rightIndex) {

       

if

(*q ==

endc) {             ne

++

;         }         q

++

;      }

     

return

substrnumREC(text, leftIndex, mid-

1

, beginc, endc) \          

+ substrnumREC(text, mid, rightIndex, beginc, endc) + nb *

ne;   }   }

void

test(

int

(*fun)(

char

* ,

char

,

char

)){

 

char

*text =

"

ABCAAB

"

;   printf(

"

text = %s\n

"

, text);   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

B

"

, (*fun)(text,

"

A

"

,

"

B

"

));   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

A

"

, (*fun)(text,

"

A

"

,

"

A

"

));



 

char

*empty =

""

;   printf(

"

text = %s\n

"

, empty);   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

B

"

, (*fun)(empty,

"

A

"

,

"

B

"

));   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

A

"

, (*fun)(empty,

"

A

"

,

"

A

"

));



 

char

*two =

"

AA

"

;   printf(

"

text = %s\n

"

, two);   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

B

"

, (*fun)(two,

"

A

"

,

"

B

"

));   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

A

"

, (*fun)(two,

"

A

"

,

"

A

"

));



 

char

*zero =

"

ADTFGC

"

;   printf(

"

text = %s\n

"

, zero);   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

B

"

, (*fun)(zero,

"

A

"

,

"

B

"

));   printf(

"

以字母 %c 开头， %c 结尾的子串数目为: %d.\n

"

,

"

A

"

,

"

A

"

, (*fun)(zero,

"

A

"

,

"

A

"

));  

 

/*

NULL 参数的断言测试，因为总是会失败导致程序退出，所以这里注释掉；可以去掉注释查看运行结果   printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\n", "A", "B", (*fun)(NULL, "A", "B"));  

   

*/

四、 结论：

举这样一个字符串问题的例子是为了说明什么呢? 主要是因为，我认为它非常生动地演示了字符串问题的几种主要思路和算法：

蛮力法、分治法、动态规划法。

另外，还有一种算法，是对字符串进行预处理，比如高效字符串匹配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)。

=========================

尚学堂--软件开发免费试学时间

Java｜Android｜Web前端

报名有礼：

1. 获得千元助学金

2. 获得价值万元的视频教材

3. 免费试学七天

免费试学时间：

每周二、四、六

上课地点：

陕西省西安市高新区科技二路西安软件园天泽大厦五楼

联系方式：

QQ：3500819260

电话:15029923798（微信同号）

参与方法：

1. 点击『

阅读原文

』提交信息

2. 公众号后台回复『

试听

』

即可获得免费试学机会；两人同行，更多豪礼相送；名额有限，先到先得。

学校组团参加的同学有车接送，接送地点发至后台由工作人员处理。

=========================

关注尚学堂--轻松学编程

每天海量编程学习资料等你来领

Java | Web | Adnroid

更多阅读：

Java案例_猜数字小游戏

Java基础知识之接口与程序示例

学习Java开发少走弯路的几个要点

点击下方

"阅读原文"

，

获取免费听课名额

• V神(Vitalik Buterin)希望以太社区基金实现炒作
• 天津：１６９家重点监测企业初一实现销售收入１.７亿元
• 绽放冬奥赛场，斯洛文尼亚实现奖牌突破
• 100多年前，杭州就有了\＂地铁\＂!这个地方实现轨交、公交双覆盖
• 银行存款方式你懂吗？怎么实现正确理财日入上百
• 最近很容易被意外之财砸中的星座，你的发财梦终于要实现了
• 78岁天津股神曝:“三不卖七不买”,字字珠玑,背熟5句实现千万本金
• 蜜蜂养殖技术｜对实现规模化养蜂的八点建议
• 依靠自身辛勤劳动实现脱贫 贫困户乐享产业红利
• Magic Leap 创始人承诺：5年内实现全息投影直播