HDU 5672 String(尺取法) - dblank

HDU 5672 String(尺取法)

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

 

Input

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

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

 

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

 

Source
题意:给你一个字符串,问你有多少子串包含k个不同的字母。
思路:如果有一段字符刚刚好满足条件,那么后面的包含这个串的子串全部满足,我们可以尺取l和r,对于一个r满足的话,后面len  -  r + 1个子串也满足,然后更新l就可以了,因为l和r是分开更新的,所以复杂度是O(n)。
#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<queue>  
#include<map>  
#include<vector>  
#include<cstring>  
#include<cmath>  
using namespace std;  
typedef long long ll;  
const int INF = 0x3f3f3f3f;  
const double  pi = acos(-1.0);  
const int N = 1e6 + 10;  
char s[N];  
int main()  
{  
    int t, k, vis[40];  
    cin>>t;  
    while(t--)  
    {  
        scanf("%s", s);  
        scanf("%d", &k);  
        memset(vis, 0, sizeof(vis));  
        int l = 0, r = 0, len = strlen(s), temp, num = 0;  
        ll ans = 0;  
        while(l<len)  
        {  
            while(r < len && num < k)  
            {  
                temp = s[r] - 'a';  
                if(!vis[temp])  
                    num++;  
                vis[temp]++;  
               r++;  
            }  
            if(num<k)  
                break;  
            ans += len - r + 1;  
            temp = s[l] - 'a';  
            vis[temp]--;  
            if(vis[temp]==0)  
                num--;  
            l++;  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}  

 

相关文章

发表新评论