HDU 5672 String

今天药忘吃喽~ 2022-08-21 10:41 14阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5672][http_acm.hdu.edu.cn_showproblem.php_pid_5672]

题目大意：给你一个字符串，你要找出它的所有包含k个不同字母的子串

解题思路：尺取法，i表示子串的起点，j表示终点，length为给你的字符串的长度  
1.先将j向后查找，当查找到字符子串有k个不同字母时停止，答案数加上length-j，  
2.然后再将i向后推，i每向后推一位如果i到j的子串仍有k个不同字母，则答案数再加length-j，一直推到i到j这个串中没有k个不同字母，  
然后再进行步骤1重复上述过程直到j和i都到结尾  
至于为什么加上 length-j  
因为对于从i开始，必须包含i到j这个串的子串最多有length-j个，  
我们在这里相当于枚举开头i。

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    char a[1000005];
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            scanf("%s",a);
            int k;
            RI(k);
            int len=strlen(a);
            int dif=0;
            int diff[30];
    
            mem(diff);
    
            LL ans=0;
            int i=-1,j=-1;
    
    
            for(; i<len; i++)
            {
                if(i>=0)
                {
                    while(i<=j&&dif==k)
                    {
    
                        diff[a[i]-'a']--;
                        if(diff[a[i]-'a']!=0)
                        {
                            ans+=len-j;
                            i++;
                        }
                        else dif--;
                    }
                }
    
                while(j<len)
                {
                    diff[a[++j]-'a']++;
                    if(diff[a[j]-'a']==1)  dif++;
                    if(dif==k) break;
                }
                ans+=(len-j);
            }
    
            cout<<ans<<endl;
        }
    
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5672]: http://acm.hdu.edu.cn/showproblem.php?pid=5672