查找以指定字符开始和结尾的子串数量

【算法设计与分析基础3.2-9】

在一段给定的文本中查找以A开始，以B结尾的子串的数量（例如，在CABAAXBYA中有4个这样的子串）。

【算法】

以字符‘B’结尾的子串的个数等于字符‘B'左侧字符串中‘A’的数量。

如：

C A B A A X B Y A

1 2

以第一个‘B’为结尾的子串个数为左侧’A‘的个数，故只有一个子串：AB。

C A B A A X B Y A

1 2

字符串中第二个’B'左侧有3个‘A'，所以有三个子串，即：ABAAXB， AAXB，AXB。

【时间复杂度】

只需要遍历一次字符串即可，故时间复杂度为：O（n）

【代码】

#include 
  
   
#include 
   
     #include 
    
      int SubString(char *str, int n) { int ANum, sumNum; char c; ANum = 0; sumNum = 0; for(int i = 0; i < n; i++) { if(str[i] == 'A') ANum++; if(str[i] == 'B') sumNum += ANum; } return sumNum; } int main(void) { char str[] = "CABAAXBYA"; int n = strlen(str); printf("%d\n", SubString(str, n)); }