问题描述

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。

在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。

给定一个字符串 S 和两个字符 c_1、c_2，请你计算 S 有多少个以 c_1 开头、c_2 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数 K。 第二行包含一个字符串 S 和两个字符 c_1、c_2。

输出格式

一个整数代表答案。

样例输入

4 
abababdb a b

样例输出

6

样例说明

符合条件的子串如下所示： [abab] [ababab] [abababdb] [abab] [ababdb] [abdb]

评测用例规模与约定

对于 20% 的数据，2 \le K \le |S| \le 10000。 对于 100% 的数据，2 \le K \le |S| \le 5\times 10^5。 S 只包含小写字母。c_1 和 c_2 都是小写字母。 |S| 代表字符串 S 的长度。

这道题要求很简单，就是找到全部大于或等于K且首字母和尾字母与给定的首字母和给定的尾字母相同的全部子串

使用什么方法?

子串以及不关心子串的内容和子串的内有多少个字符，我首先想到了贡献计算，但是我没想到好的解决办法，我第一次思考出来会使用双重循环，这显然会超时，所以我整理了一下已知条件:

1.子串长度等于或者大于K

2.我只关心子串的头和尾，使用贡献计算

3.子串的头和尾要满足一定的条件

贡献计算的实现

既然只关心头和尾，用双指针，定义一个左指针left，一个右指针right

因为题目说要满足子串长度大于或等于K，即满足:

其中加1是补全字符数量，如 left = 0，right = 1，1-0=1但实际有两个字符，所以加上1

转换一下就有:

(L = left,R = right)

R-L+1 \ge k
R-L \ge k-1
R - k + 1 \ge L

也就是：

这样子就能确定L的位置了，为了避免使用两层循环

所以如果只对R进行循环而利用上面的式子也能做到对L进行循环，又L的取值范围为大于等于0，所以如果

L小于零则要跳过这个数值

这里我们可以使用预存的办法，我一开始并不知道R是否等于c2，但是我知道L是否等于c1,这只需要加一步

判断就行了，我先把L出现多少次c1保留起来，存在预存变量pre中，再检查R是否为c2,如果为c2，因为L与R

满足中间相隔K的关系，所以则L可以与之配对，则ans+=pre，如果不为c2，ans就不赋值，pre记录前面出现

的次数

因为R和L的关系恒定，所以前面的L都能与后面R配对，R一旦是c2，那么答案就要增加前面预存c1的个数pre

就能在只经历一次循环就能得到答案的要求

下面是代码展示:

<code>#include <stdio.h>
#include <string.h>
char list[500000];
int main(void)
{
	long long int k;
	char c1,c2;
	long long int pre=0,ans=0;//预存，答案 
	scanf("%lld",&k);
	scanf("%s",list);
	scanf(" %c",&c1);
	scanf(" %c",&c2);
	
	long long int left,right,len;
	len = strlen(list);
	for(right=0;right<len;right++)
	{
		left = right + 1 - k;
		if(left>=0)
		{
			if(list[left] == c1) pre++;//预存用来存放找到的c1 
			if(list[right] == c2) ans += pre;//当右值等于C2时，预存中的全部C1都能与之配对，答案加pre 
		}
	}
	printf("%lld",ans);
	return 0;
}</code>