字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。
现给定字符串，问一共可以形成多少个PAT？
输入格式：
输入只有一行，包含一个字符串，长度不超过105，只包含P、A、T三种字母。
输出格式：
在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。
输入样例：
|
1 |
APPAPT |
输出样例：
|
1 |
2 |
注意优化……三重循环能解，但是一定会超时！
思路大体是这样的：
- 读入字符串，通过声明的结构体数组count实现对字符串的重新储存和计数，重新处理即为对相邻重复字符串的合并与计数。
- 从count末端开始，把T的计数向前依次叠加至距离其前最近的A的next上，获得每个A后有多少个T。
- 仍然从count末端开始，把每个A所对应的num*next，即此处后AT总个数向前叠加至A的num上（这里我当时应该是写烦了，感觉最好是P的next上，尽管效果都一样），这样每个A的位置就储存了其（包括它自身）后方共有多少个AT。
- 从count前端开始，累加（每个P的num*其后第一个A的num）计算PAT的数量。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include<stdio.h> struct { char c; long num; long next; }count[100001],*pcount,*pcount_e; int main() { char buf[100001]=" "; int i,j,k; long result=0,count_t=0,count_a=0; pcount=count; gets(buf); count[0].c=buf[0]; count[0].num++; for(i=1;buf[i];i++) { if(buf[i]==pcount->c) { (pcount->num)++; } else { pcount++; pcount->c=buf[i]; pcount->num++; } } pcount_e=pcount+1; pcount_e->c='T'; pcount_e->num=0; for(i=0;pcount+i>count;i--) { if((pcount+i)->c=='T') { (pcount+i)->num+=count_t; count_t=(pcount+i)->num; } else if((pcount+i)->c=='A') { (pcount+i)->next=count_t; (pcount+i)->num*=(pcount+i)->next; (pcount+i)->num+=count_a; count_a=(pcount+i)->num; } } /* count_t=0; for(i=0;pcount+i>count;i--) { if((pcount+i)->c=='A') { for(j=i+1;pcount+j<=pcount_e;j++) { if((pcount+j)->c=='T') { (pcount+i)->next=(pcount+j)->num; break; } } (pcount+i)->num*=(pcount+i)->next; (pcount+i)->num+=count_t; count_t=(pcount+i)->num; } }*/ for(i=0;count+i<pcount-1;i++) { if(count[i].c=='P') { for(j=i+1;count+j<pcount_e;j++) { if(count[j].c=='A') { result+=(count[i].num*count[j].num); result%=1000000007; break; } } } } /* for(i=0;count+i<pcount_e;i++) { temp[0]=1; if(count[i].c=='P') { temp[0]*=count[i].num; temp[1]=0; for(j=i+1;count+j<pcount_e;j++) { if(count[j].c=='A') { temp[2]=1; temp[2]*=count[j].num; temp[2]*=count[j].next; temp[1]+=temp[2]; } } temp[0]*=temp[1]; result+=temp[0]; result%=1000000007; } }*/ printf("%dn",result); } |