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