字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。
现给定字符串，问一共可以形成多少个 PAT？
输入只有一行，包含一个字符串，长度不超过1，只包含 P、A、T 三种字母。
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。
APPAPT
2#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int maxn = 100010, mod = 1000000007; char s[maxn]; int p[maxn] = { 0 }; int main() { int N,K,L=0; int count = 0; scanf("%s", &s); N = strlen(s); //printf("%d", N); for (int i = 0; i < N; i++) { if (i > 0) { p[i] = p[i - 1]; } if (s[i] == ‘P‘) { p[i]++; } } int ans = 0, numT = 0; for (int i = N - 1; i > 0; i--) { if (s[i] == ‘T‘) { numT++; } else if (s[i] == ‘A‘) { ans = (ans + p[i] * numT) % mod; //ans = ans % mod; } } printf("%d", ans); system("pause"); return 0; }
注意点：先统计每个位置上前面有多少个P，再从后往前遍历，遇到T就计数，遇到A就计算。如果再从尾到头遍历T而不是边遍历边计算，容易超时。
原文：https://www.cnblogs.com/tccbj/p/10364690.html