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 ;
}