hdu5672 尺取法

StringTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1077    Accepted Submission(s): 348

Problem Description

There is a string S.S only contain lower case English character.(10≤length(S)≤1,000,000)
How many substrings there are that contain at least k(1≤k≤26) distinct characters?

 

Input

There are multiple test cases. The first line of input contains an integer T(1≤T≤10) indicating the number of test cases. For each test case:

The first line contains string S.
The second line contains a integer k(1≤k≤26).

 

Output

For each test case, output the number of substrings that contain at least k dictinct characters.

 

Sample Input

2 abcabcabca 4 abcabcabcabc 3

 

Sample Output

0 55

题目大意：给你一个由小写字母组成的字符串，然后给你一个k，表示至少有k个不同的字母，问满足该条件的

所有的字串的数目。

思路分析：尺取法基本思路是：

            1.初始化左右端点

　　　　2.不断扩大右端点，直到满足条件

　　　　3.如果第二步中无法满足条件，则终止，否则更新结果

　　　　4.将左端点扩大1，然后回到第二步

在本题就是先不断扩大右端点，直到满足cut>=k,然后开始移动左端点，并累加子串数目，弱不满足，则继续

右移右端点，直到下一次满足条件。

代码：#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
const int maxn=30;
int q[maxn];
int main()
{
    int T;
    string s;
    int k;
    scanf("%d",&T);
    while(T--)
    {
        cin>>s;
        scanf("%d",&k);
        int l=s.length();
        int t=0,cut=0;
        long long  sum=0;
        memset(q,0,sizeof(q));
        for(int i=0;i<l;i++)
        {
            int p=s[i]-'a';
            if(q[p]==0)
                cut++;
            q[p]++;
            while(cut>=k)
            {
                sum+=l-i;
                q[s[t]-'a']--;
                if(q[s[t]-'a']==0)
                    cut--;
                t++;//t代表子串开始位置
            }
        }
     cout<<sum<<endl;
    }
    return 0;
}