题目链接：https://pintia.cn/problem-sets/994805260223102976/problems/994805282389999616
字符串 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
分析：
从前往后算出每个位置及之前位置所有P的个数
从后往前算出每个位置及之后位置所有T的个数
遍历各位置，如果是A，PAT总数加上此位置之前P的个数乘以此位置之后T的个数（结果mod1000000007 ）
1 #include <stdio.h> 2 #include <string.h> 3 #define mood 1000000007 4 char s[100010]; 5 int nump[100010] = {0}; 6 int numt[100010] = {0}; 7 8 int main() 9 { 10 scanf("%s", s); 11 nump[0] = 0, numt[strlen(s) - 1] = 0; 12 if (s[0] == ‘P‘) 13 nump[0] = 1; 14 if (s[strlen(s) - 1] == ‘T‘) 15 numt[strlen(s) - 1] = 1; 16 for (int i = 1; i < strlen(s); i++) // 求出每个位置及之前所有位置P的个数 17 { 18 if (s[i] != ‘P‘) 19 nump[i] = nump[i - 1]; 20 else 21 nump[i] = nump[i - 1] + 1; 22 } 23 for (int i = strlen(s) - 2; i >= 0; i--)// 求出每个位置及之后所有位置T的个数 24 { 25 if (s[i] != ‘T‘) 26 numt[i] = numt[i + 1]; 27 else 28 numt[i] = numt[i + 1] + 1; 29 } 30 int sum = 0; 31 for (int i = 0; i < strlen(s); i++) // 遍历 32 { 33 if (s[i] == ‘A‘) 34 sum = (sum + (nump[i] % mood * numt[i] % mood) % mood) % mood; 35 } 36 printf("%d\n", sum); 37 return 0; 38 }
原文：https://www.cnblogs.com/sqdtss/p/12774030.html