二分法求解

解题思路:首先字符串是s，两个连接字符是c1和c2而我们可以发现对于每个c1都会有一个c2（下标记为pos）可以使得pos之后的字符串都能满足条件，发现了没有很像二分的思路，先用a，b数组保存c1,c2的下标再选定a[i]对b做二分即可（注意一个都没有的情况说明之后都找不到任意b[i]-a[i]+1>=k了）

注意事项:c1和c2可能相等，保存下标的时候不能用if else结构

参考代码:

#include<iostream>

#include<string>

using namespace std;

string s;

long long int a[500000], b[500000], k, sum = 0, j=0, k1=0;

char t1, t2;

int main()

{

    cin >> k >> s >> t1 >> t2;

     for (int i = 0; i <= s.size() - 1; i++)

     {

         if (s[i] == t1)

         {

             a[j] = i;

             j++;

         }

         if (s[i] == t2)

         {

             b[k1] = i;

             k1++;

         }

     }

     for (int i = 0; i <= j - 1; i++)

     {

     long long int l = 0, r = k1-1, mid, sum2=k1;

     if (b[k1 - 1] - a[i] + 1 < k)

        break;

     while (l <= r)

     {

     mid = (l + r) / 2;

         if (b[mid] >= a[i]+k-1)

         {

             r = mid - 1;

             sum2 = mid;

         }

         else

              l = mid + 1;

         }

        sum += k1 - sum2;

     }

     cout << sum;

}