PAT (Advanced Level) Practice 1093 Count PAT's (25 分) 淩宸1642

題目描述：

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.

譯：字元串

APPAPT

包含 2 個子串

PAT

。第一個由第二、第四和第六個字母組成，第二個由第三、第四和第六個字母組成。現在給你任意的字元串，你應該找出這個字元串中包含子串

PAT

的個數。

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only

P

,

A

, or

T

..

譯：每個輸入檔案包含一個測試。對于每個用例，在一行中給定一個隻包含

P

A

或者

T

字母并且長度不超過 105 的字元串。

Output Specification:

Sample Input (樣例輸入):

APPAPT
           

Sample Output (樣例輸出):

2
           

The Idea：

• 思考子串

  P

  ，

  PA

  PAT

  之間的關系。
• 從左至右依次周遊字元串，統計上述子串

  P

  PA

  PAT

  的數量，當遇到字母

  P

  ，則

  P

  的數目自增 ； 當遇到

  A

  則此時有多少個

  P

  PA

  的數量增加多少個；當遇到

  T

  PA

  PAT

  的數量增加多少個。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
ll p = 0 , pa = 0 , pat = 0 ;
string s ;
ll mod = 1000000007 ;

int main(){
	cin >> s ;
	for(int i = 0 ; i < s.size() ; i ++){
		if(s[i] == 'P') p = (++p) % mod ;
		else if(s[i] == 'A') pa = (pa + p) % mod ;
		else pat = (pat + pa) % mod ;
	}
	cout << pat << endl ;
	return 0 ;
}