3
【思路】这道题应该是用bfs来做，但是只是浅浅一眼就润了，后面没有时间补了，悲，主要bfs不熟练，不太想花时间
试题 G: 子串简写【问题描述】程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation alization 简写成 i18n， Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法 （长度小于 K 的字符串不配使用这种简写）。给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写？【输入格式】第一行包含一个整数 K。第二行包含一个字符串 S 和两个字符 c1 和 c2。【输出格式】一个整数代表答案。【样例输入】4abababdb a b【样例输出】6【思路】这道题直接暴力肯定是不太行的感觉，5×10^5 应该是会炸的，这里我把目标的字符抽离出来只简单记录好在原来的字符串中的位置，分别用两个数组来存储，然后对 a 的位置一个一个从前往后进行查找，我们的目标是找每一个 a 往后数 k-1 个位置之后有多少个 b 出现，所以简单while对比一下就好，由于我们已经把 a 还有 b 抽离出来存储位置，所以我们能够直接定位到 b 的位置的同时，也能够快速查询到后面还剩下多少个 b 。
【代码】#includeusing namespace std;const int N = 100010;typedef long long LL;int a[N],b[N];int main(){int k;cin>>k;string s;char aa,bb;cin>>s;scanf(" %c %c",&aa,&bb);//cout