题目

The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT's contained in the string.

Input Specification:
Each input file contains one test case. For each case, there is only one line giving a string of no more than characters containing only P, A, or T.

Output Specification:
For each test case, print in one line the number of PAT's contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:
APPAPT
Sample Output:
2

---

题目描述

这道题目描述的是，给予一个仅包含‘P’、‘A’和‘T’三个字母的字符串，然后统计其中可以组成“PAT”串的子串的个数。例如，题目例子：“APPAPT”，有两个可以组成“PAT”的子串。（分别是第2，4，6个字符和第3，4，6个字符）

题目分析

  这道题目换个角度想就是一道排列组合的题目，假设字符串str[i]=='A'（第i位为“A”），以第i位的A来组成的字符串“PAT”个数 = 这个“A”的前面字符“P”的数量 * 这个“A”的前面字符“T”的数量。这道题则只需统计所有字符“A”前面的字符“P”与后面“T”字符的数量，然后相乘累加即可。
  如果以常规方法，枚举字符串里每个字符“A”，然后再分别从头以及从尾计算其“P”和“T”字符的个数，其计算复杂度会达到，算法会超时。因此，需要利用字符串里的一些递推关系，假设numP[i]为第i个字符前“P”字符的个数（包含本身），则：

因为numP[i-1]已经包含了从字符串0~i-1位字符串“P”的数量，只需要再看看当前的字符是否为P即可。同理也只需以类似方法记录字符后面“T”的数量；然后再从头开始枚举，遇到字符“A”再将其numP与numT相乘累加即可。

#include<stdio.h>
#include<string.h>

char str[100010];
int numP[100010];

int main() {
    int length, rightNumT;
    long long result;
    
    scanf("%s", str);
    length = strlen(str);
    
    result = 0;
    memset(numP, 0, sizeof(numP));
    for (int i = 0; i < length; i++) {
        if (i != 0)
          numP[i] = numP[i - 1];
        if (str[i] == 'P')
          numP[i]++;
    }
    
    rightNumT = 0;
    for (int i = length - 1; i >= 0; i--) {
        if (str[i] == 'T')
          rightNumT++;
        else if ( str[i] == 'A' )
          result = (result + numP[i] * rightNumT) % 1000000007;
    }

    printf("%d\n", result);
    
    return 0;
}

---

总结

   这道题因为每个“PAT”的组成需要字符‘A’，因此以字符‘A’作为中心，计算前面‘P’和后面‘T’的个数相乘；换个其他字符，例如我设置一个数组计算从该字符往后字符“A”与字符“T”的个数，然后扫描数组，当遇到字符“P”时，result += 后面字符“A”的个数 * 后面字符“T”的个数，这样也是可行的。
   该道题目是如何利用递推关系，来快速统计相应字符的个数。这里是设置一个数组来记录从头至当前位置，某字符的个数，那么当前位置i的个数就只需前一个i-1位置的个数（已经有了从头至i-1位的个数），再判断当前第i位是否也是该字符，即可统计到从头至今位置某特定字符的个数。
   在做该道题目的时候，一开始曾使用过利用两个数组分别记录前面“P”与后面“T”的个数，可是仅通过了部分测试点；也在网络上看到也是通过两个数组来解题，可以通过全部测试点。（还没想到出错的原因）网络上柳神有无需使用数组也可通过的版本，也还没认真了解过其过程。我最后是依据书本方法来通过该道题。