本文共 1344 字，大约阅读时间需要 4 分钟。

为了解决寻找字符串中 PAT 子串的问题，我们可以使用以下方法：

方法思路

问题要求我们在一个只包含字符 'P'、'A'、'T' 的字符串中找到所有可能的 PAT 子串的数量。我们可以通过以下步骤来解决这个问题：

这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度。通过预先计算左右两边的数量，避免了多次遍历，从而提高了效率。

解决代码

#include 
   
    using namespace std;int main() {    string s;    cin >> s;    int n = s.size();    if (n == 0) return 0;    vector
    
      left_p(n, 0);    vector
     
       right_t(n, 0);    // 计算左边的P数量累积    left_p[0] = (s[0] == 'P') ? 1 : 0;    for (int i = 1; i < n; ++i) {        left_p[i] = left_p[i-1] + (s[i] == 'P' ? 1 : 0);    }    // 计算右边的T数量累积    right_t[n-1] = (s[n-1] == 'T') ? 1 : 0;    for (int i = n-2; i >= 0; --i) {        right_t[i] = right_t[i+1] + (s[i] == 'T' ? 1 : 0);    }    int result = 0;    for (int i = 0; i < n; ++i) {        if (s[i] == 'A') {            result = (result + left_p[i] * right_t[i]) % 1000000007;        }    }    printf("%d", result);    return 0;}
     
    
   

代码解释

这种方法通过预先计算左右两边的数量，确保了每个 'A' 的计算是高效准确的，从而能够快速解决问题。