查找以指定字符開始和結尾的子串數量

【算法設計與分析基礎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));
}