有几个PAT

描述

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入

输入只有一行，包含一个字符串，长度不超过10⁵，只包含P、A、T三种字母。

输出

在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

样例输入

APPAPT

样例输出

 1 #include <bits/stdc++.h>  //动态规划判断A之前有多少个P 和A之后有多少个T
 2                           //求后面这个反过来求T之前有多少个A
 3 using namespace std;
 4 const int N=1e5+5;
 5 typedef long long ll;
 6 int main()
 7 {
 8     ios::sync_with_stdio(false);
 9     string ss;
10     cin>>ss;
11     ll dp1[N],dp2[N];
12     memset(dp1,0,sizeof(dp1));
13     memset(dp2,0,sizeof(dp2));
14     if(ss[0]=='P')
15         dp1[0]=1;
16     else dp1[0]=0;
17     ll num=0;ll u=0;
18     for(int i=1;i<ss.size();i++){   //这个位置的A前面又多少个P
19         if(ss[i]=='A'){
20             dp1[i]=dp1[u]+num;
21             num=0;
22             u=i;   //u  标记前面的A
23 //            printf("%d %d
",i,dp1[i]);
24         }
25         if(ss[i]=='P') num++;
26     }
27     ll len=ss.size()-1;
28     if(ss[len]=='T')
29         dp2[len]=1;
30     else dp2[len]=0;
31     num=0;u=len;
32     for(int i=ss.size()-2;i>=0;i--){  //这个位置的A后面有多少个T
33         if(ss[i]=='A'){
34             dp2[i]=dp2[u]+num;
35             num=0;
36             u=i;
37         }
38         if(ss[i]=='T'){
39             num++;
40         }
41     }
42 //    printf("%d   
",dp1[3]);
43 //    for(int i=0;i<=len;i++){
44 //        printf("dp1[i]=%d  dp2[i]=%d
",dp1[i],dp2[i]);
45 //    }
46     ll sum=0;
47     for(int i=0;i<=len;i++){
48         if(dp1[i]!=0&&dp2[i]!=0){
49             sum=(sum+dp1[i]*dp2[i])%1000000007;
50         }
51     }
52     printf("%lld
",sum);
53     return 0;
54 }

View Code