1040 有几个PAT （25 分）

1040 有几个PAT （25 分）

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

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

输入格式：

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

输出格式：

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

输入样例：

APPAPT

输出样例：

2

参考代码：

#include#includeconst int maxn = 100010;char str[maxn];int leftNumP[maxn];int main(){ scanf("%s", str); int len = strlen(str); for (int i = 0; i < len; ++i) { if(i > 0){ leftNumP[i] = leftNumP[i - 1]; } if(str[i] == 'P'){ leftNumP[i]++; } } int ans = 0, rightNumT = 0; for (int j = len -1; j >= 0; --j) { if(str[j] == 'T'){ rightNumT++; }else if(str[j] == 'A'){ ans = (ans + rightNumT * leftNumP[j]) % 1000000007; } } printf("%d\n", ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。