題目

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’三個字母的字符串，然后統(tǒng)計其中可以組成“PAT”串的子串的個數(shù)。例如，題目例子：“APPAPT”，有兩個可以組成“PAT”的子串。（分別是第2，4，6個字符和第3，4，6個字符）

題目分析

??這道題目換個角度想就是一道排列組合的題目，假設字符串str[i]=='A'（第i位為“A”），以第i位的A來組成的字符串“PAT”個數(shù) = 這個“A”的前面字符“P”的數(shù)量 * 這個“A”的前面字符“T”的數(shù)量。這道題則只需統(tǒng)計所有字符“A”前面的字符“P”與后面“T”字符的數(shù)量，然后相乘累加即可。
??如果以常規(guī)方法，枚舉字符串里每個字符“A”，然后再分別從頭以及從尾計算其“P”和“T”字符的個數(shù)，其計算復雜度會達到，算法會超時。因此，需要利用字符串里的一些遞推關系，假設numP[i]為第i個字符前“P”字符的個數(shù)（包含本身），則：

因為numP[i-1]已經(jīng)包含了從字符串0~i-1位字符串“P”的數(shù)量，只需要再看看當前的字符是否為P即可。同理也只需以類似方法記錄字符后面“T”的數(shù)量；然后再從頭開始枚舉，遇到字符“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’的個數(shù)相乘；換個其他字符，例如我設置一個數(shù)組計算從該字符往后字符“A”與字符“T”的個數(shù)，然后掃描數(shù)組，當遇到字符“P”時，result += 后面字符“A”的個數(shù) * 后面字符“T”的個數(shù)，這樣也是可行的。
???該道題目是如何利用遞推關系，來快速統(tǒng)計相應字符的個數(shù)。這里是設置一個數(shù)組來記錄從頭至當前位置，某字符的個數(shù)，那么當前位置i的個數(shù)就只需前一個i-1位置的個數(shù)（已經(jīng)有了從頭至i-1位的個數(shù)），再判斷當前第i位是否也是該字符，即可統(tǒng)計到從頭至今位置某特定字符的個數(shù)。
???在做該道題目的時候，一開始曾使用過利用兩個數(shù)組分別記錄前面“P”與后面“T”的個數(shù)，可是僅通過了部分測試點；也在網(wǎng)絡上看到也是通過兩個數(shù)組來解題，可以通過全部測試點。（還沒想到出錯的原因）網(wǎng)絡上柳神有無需使用數(shù)組也可通過的版本，也還沒認真了解過其過程。我最后是依據(jù)書本方法來通過該道題。