题目描述

输入一个包含P，A，T三个字符的字符串，输出其包含的PAT字符串个数

样例

输入样例

APPAPT

输出样例

2

思路：

从枚举开始尝试，可以发现输出就是满足合法顺序的PAT

故需要记录每个位置的顺序信息，可以尝试对字符串正向扫描一次，并在每个位置记录前缀P个数leftP[i]

保证了各个位置记录了P的顺序信息后，对字符串从末尾向前扫描，记录后缀T的个数

这次扫描，不需要记录T的位置信息，只要边扫描T的位置信息rightNumT边计算Sum即可

计算方案是 
sum = ( sum + leftP[i] * rightNumT ) % MOD

C++ 代码

#include<iostream>
using namespace std;
string input;
const int MOD = 1000000007;
const int N = 100010;
int leftP[N] = {0};
int ans = 0;
int main()
{
    cin>>input;
    for(int i = 0;i<input.size();i++)//正向扫描
    {
        if(i>0)leftP[i] = leftP[i-1];//先直接继承前缀P的个数
        if(input[i]=='P')leftP[i]++;
    }
    int rightNumT = 0;
    for(int i = input.size()-1;i>=0;i--)//从末尾向前扫描，边扫描边计算
    {
        if(input[i]=='T')rightNumT++;
        else if(input[i]=='A')
            ans = (ans+leftP[i]*rightNumT)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}