hdu 5672 String(尺取)

422 阅读 0 评论 279 点赞

我是靠谱客的博主平常黑裤，这篇文章主要介绍hdu 5672 String(尺取)，现在分享给大家，希望可以做个参考。

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
  
  
solution：
	求有多少个子串，包含有至少k个不同的字母，我们发现，如果i~j是恰好含有k个字母的区间，那么对于k(j<k<=n)，i~k是含有至少k个不同字母的子串，那么对于每一个左边界，我们都可以找到一个最小的右边界，使得这个区间恰好含有k个字母，然后统计以这个左边界符合条件的子串个数，找到右边界，用尺取法即可。
#include<cstdio>
#include<cstring>
using namespace std;
char s[1000200];
int vis[30];
int main()
{
    int t,k;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s%d", s,&k);
        int len = strlen(s), sum = 0, r = -1;
        long long ans = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < len; i++)
        {
            while (sum < k&&r+2<=len)
            {
                r++;
                vis[s[r] - 'a']++;
                if (vis[s[r] - 'a'] == 1)sum++;
            }
            if (sum==k)ans += len - r;
            vis[s[i] - 'a']--;
            if (vis[s[i] - 'a'] == 0)sum--;
        }
        printf("%I64dn", ans);
    }
}