第十四届省赛真题-子串简写踩坑记录

坑真的很多，最开始是用两个for嵌套用暴搜然后超时了，改了这种方法，一踩一个坑。

先全部找出C1C2的位置并且记录数量，用C1的位置比对C2的位置，找到C1位置+K-1大于大于C2位置的时候，就把往后的C2字符数量全部加起来，然后跳出C2的循环去下一个C1的位置。这种方法减少了循环次数。

注意：C2没有了之后还可能会有C1，所以全部C2加完后要退出所有循环。

C1C2可能相等，会造成前面搜索C2的时候为0，导致结果为0.

最后输出的子串会很长，光int不够。
参考代码:

#include <stdio.h>

#include <string.h>

char S[5 * 100000 + 1];

int a[500000],b[500000];

int main() {

int K;

scanf("%d", &K);

char c1, c2;

scanf("%s %c %c",&S, &c1, &c2);

getchar();

int len = strlen(S);

long long int t=0;//最后的输出数据会很大，所以一定要+long，不然光int不够最后输出数据会变为负数 

int x=0,y=0;

//找出c1,c2的所在位置以及数量 

for (int i = 0; i < len; i++) {

if (S[i] == c1) {

a[x]=i;

x++;

} else if (S[i] == c2) {

b[y]=i;

y++;

}

//当存在非字母的符号时，使上一个存储的c1位置+1 

else if (S[i] <'a'||S[i]>'z') {

if(i<=a[x-1]+K-1) a[x-1]++;

}

}

int j=0,k;

for(int i=0; i<x; i++) {

//判断c1，c2是否相等，！这是个坑 

if(c1!=c2) {

k=y;

for(; j<k; j++) {

if(a[i]+K-1<=b[j]) {

t=t+y-j;

j--;

k=0;

}

}

if(j==y) break;

} else {

k=x;

for(; j<k; j++) {

if(a[i]+K-1<=a[j]) {

t=t+x-j;

j--;

k=0;

}

}

if(j==x) break;

}

}

printf("%ld\n",t);

return 0;

}