题目
字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。
现给定字符串，问一共可以形成多少个PAT？
输入格式：
输入只有一行，包含一个字符串，长度不超过105
，只包含P、A、T三种字母。
输出格式：
在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。
输入样例：APPAPT
输出样例：2
具体内容可访问PAT网站：题目链接。
算法分析
如果使用暴力破解算法，时间复杂度为O(n^3)，显然不是最优的方法。
可以使用递推的思想来解决该问题。
已知一个长度为n的字符串中“PAT”的个数为sum，如果在这个字符串后添加一个字符后组成的新的字符串中“PAT”的个数会是多少呢？
如果添加的字符为‘P’，新字符串的“PAT”个数不发生变化。
如果添加的字符为‘A’，新字符串的“PAT”个数不发生变化。
如果添加的字符为‘T’，新字符串的“PAT”个数可能发生变化。而发生变化的数量是因为添加的‘T’构成了新的“PAT”。想要知道新构成的“PAT”的数量，则需要知道旧字符串中“PA”的数量，因为旧字符串中“PA”的数量等于新构成的“PAT”的数量。即新字符串的“PAT”个数=旧字符串中“PA”的数量+旧字符串中“PA”的数量。
想要知道旧字符串中“PA”的数量只需要使用上述的方法就可以得到，笔者就不再赘述，下文中将会用形式化方法展示算法的具体实现。
算法实现
令输入的字符串为string，其下标为[1...n]。
string[x]为string中第x位的字母，x ∈ [1, n]。
pattern为连续的字符串模式，pattern={P, PA, PAT}。在本题中，关心的字符串模式只有上述3种。
sum(x, pattern)定义：对于子字符串string[1...x]，对应字符串模式pattern的总数。其中x ∈ [0, n]，且sum[0, patter] = 0。
- 当string[x] = 'T'时：
sum(x, P) <- sum(x - 1, P)
sum(x, PA) <- sum(x - 1, PA)
sum(x, PAT) <- sum(x - 1, PAT) + sum(x - 1, PA) - 当string[x] = 'A'时：
sum(x, P) <- sum(x - 1, P)
sum(x, PA) <- sum(x - 1, PA) + sum(x - 1, P)
sum(x, PAT) <- sum(x - 1, PAT) - 当string[x] = 'P'时：
sum(x, P) <- sum(x - 1, P) + 1
sum(x, PA) <- sum(x - 1, PA)
sum(x, PAT) <- sum(x - 1, PAT)
对于一个长度为n的字符串string而言，其中PAT的数量也就是sum(n, PAT)。只需要从1-n递推地计算sum值，即可得到最终结果。因此，该算法的时间复杂度为O(n)。
代码实现
代码是由C++实现的，如下所示。
#include <stdio.h>
#include <string.h>
const int maxStringLength = 100100;
const int module = 1000000007;
char inputArr[maxStringLength] = {0};
int length = 0;
void getInput();
void output(long long result);
long long calcSum();
int main() {
long long result;
getInput();
if (length > 0) {
result = calcSum();
output(result);
} else {
output(0);
}
return 0;
}
void getInput() {
scanf("%s", inputArr);
length = strlen(inputArr);
}
void output(long long result) {
printf("%lld", result % module);
}
long long calcSum() {
long long sumP, sumPA, sumPAT;
sumP = sumPA = sumPAT = 0;
for (int i = 0; i < length; i ++) {
if (inputArr[i] == 'P') {
sumP ++;
} else if (inputArr[i] == 'A') {
sumPA += sumP;
} else {
sumPAT += sumPA;
}
}
return sumPAT;
}
