字串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

程式碼：

#include"iostream"

#include "string"

using namespace std;

int main()

{

string s;

cin >> s;

int numT = 0, numAT = 0, numPAT = 0;

for (int i = s.length(); i > 0; i--)

{

if (s[i] == "T")

++numT;

else if (s[i] == "A")

numAT = (numAT + numT) % 1000000007;

else//P

{

numPAT = (numPAT + numAT) % 1000000007;

}

}

cout

}

思路和陷阱：

三層迴圈肯定是會超時的，所以從後向前尋找T的個數，而不尋找P後面AT的個數，這樣T的個數確定後，向前遇到‘A’的話，AT的個數就會確定下來，如此，PAT就會得知，時間複雜度O（n）