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

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

【算法设计与分析基础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 <stdio.h>
#include <stdlib.h>
#include <string.h>

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));
}