KMP是匹配一个字符串是不是另外一个字符串的子串

字符串 APPAPT 中共包含两个 PAT 作为子串。

第一个子串由第二，第四和第六个字符组成，第二个子串由第三，第四和第六个字符组成。

现在给定一个字符串，请你求出字符串中包含的 PAT 的数量。

输入格式
共一行，包含一个由大写字母 P,A,T
 构成的字符串。

输出格式
输出字符串中包含的 PAT 的数量。

由于结果可能很大，请你输出对 1000000007
 取模后的结果。

数据范围
给定字符串的长度不超过 105
。

输入样例：
APPAPT
输出样例：
2

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long LL;

const LL MOD=1000000007;

string str;
vector<int> a;

int main(){
    cin>>str;

    int n=str.size();
    LL p=0,s=0,result=0;
    for(int i=0;i<n;i++){
        if(str[i]=='P')p++;

        else if(str[i]=='A'){
          a.push_back(p);   
          s+=p;
        }

        else if(str[i]=='T'){
            result=(result+s)%MOD;
        }
    }

    cout<<result<<endl;

    return 0;
}