1040. 有几个PAT（25）

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10⁵，只包含P、A、T三种字母。

输出格式：

在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

输入样例：

APPAPT

输出样例：

2

这个算法会超时，下面的改进算法可以正确通过

#include "iostream"
#include "vector"
#include "string"
#include "algorithm"

using namespace std;

int main()
{
	string input = "";
	int count = 0;
	cin >> input;

	int length = input.length();
	for (int i = 0; i < length; i++)
	{
		if (input[i] == 'P')
		{
			for (int j = i + 1; j < length; j++)
			{
				if (input[j] == 'A')
				{
					for (int k = j + 1; k < length; k++)
					{
						if (input[k] == 'T')
							count++;
						else
							continue;
					}
				}
				else
				{
					continue;
				}
			}
		}
		else
		{
			continue;
		}
	}
	cout << count%100000007;
	system("pause");
	return 0;
}

下面的算法时间短，反向思维

#include "iostream"
#include "vector"
#include "string"
#include "algorithm"

using namespace std;

int main()
{
	string input = "";
	int countP = 0;
	int countA = 0;
	int countT = 0;

	cin >> input;

	int length = input.length();
	for (int i = 0; i < length; i++)
	{
		if (input[i] == 'P')             // 记录P的个数
			countP++;
		else if(input[i] == 'A')         // 加上A前面的P的个数，记录PA的个数
			countA += countP;
		else
			countT = (countT + countA) % 1000000007;            // 同理加上T前面的PA的个数， 记录PAT的个数
	}
	cout << countT ;
	system("pause");
	return 0;
}