字符串APPAPT中包含了兩個單詞“PAT”，其中第一個PAT是第2位(P),第4位(A),第6位(T)；第二個PAT是第3位(P),第4位(A),第6位(T)。

現給定字符串，問一共可以形成多少個PAT？

輸入格式：

輸入只有一行，包含一個字符串，長度不超過105，只包含P、A、T三種字母。

輸出格式：

在一行中輸出給定字符串中包含多少個PAT。由于結果可能比較大，只輸出對1000000007取余數的結果。
輸入樣例：

APPAPT

輸出樣例：

2

錯誤代碼：

/*************************************************************************> File Name: 1040.c> Author: YueBo > Function:有幾個PAT> Created Time: 2016年11月19日 星期六 15時30分09秒************************************************************************/#include <stdio.h> #include <stdlib.h> #define NUM 1000000007 int main() {char patString[100000], ch;int i, j, k, N = 0, sum = 0;while ((ch = getchar()) != '\n') {patString[N] = ch;N++;}for (i = 0; i < N; i++) {for (j = i+1; j < N; j++) {for (k = j+1; k < N; k++) {if (patString[i] == 'P' &&patString[j] == 'A' &&patString[k] == 'T') {sum++;sum = sum % NUM;}}}}printf("%d", sum);return 0; }

這個庸俗的算法是地球人都能想到噠，下面觀察幾個量的變化，看能否想出一個新算法呢？
APPAPT（假設第一個位置是0，最后一個位置是5），aCnt表示A的數量，apCnt表示AP組合的數量，aptCnt表示APT組合的數量。

0--> pCnt = 0? paCnt = 0? patCnt = 0

1--> pCnt = 1? paCnt = 0? patCnt = 0

2--> pCnt? = 2 paCnt = 0? patCnt = 0

3--> pCnt = 2? paCnt = 0+2 patCnt = 0

4--> pCnt = 3? paCnt = 2 patCnt = 0

5--> pCnt = 3 patCnt = 2 patCnt = 2

結合下面的代碼可理解上面的過程：

/*************************************************************************> File Name: 1040_1.c> Author: YueBo > Function:> Created Time: 2016年11月19日 星期六 23時40分11秒************************************************************************/#include <stdio.h> #include <stdlib.h>#define NUM 1000000007 int main() {long long pCnt = 0, paCnt = 0, patCnt = 0;char ch;while ((ch = getchar()) != '\n') {if (ch == 'P') {pCnt++;} else if (ch == 'A') {paCnt += pCnt;} else {patCnt += paCnt;patCnt %= NUM;}}printf("%lld", patCnt);return 0; }

總結

以上是生活随笔為你收集整理的1040. 有几个PAT（25的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。