hdoj String 5672 （字元串模拟）求至少有k個不重複的字元的子串個數

String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1252    Accepted Submission(s): 415

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
        

Source BestCoder Round #81 (div.2) 問題描述

有一個 10\leq10≤長度\leq 1,000,000≤1,000,000 的字元串，僅由小寫字母構成。求有多少個子串，包含有至少k(1 \leq k \leq 26)k(1≤k≤26)個不同的字母？      

輸入描述

輸入包含多組資料. 第一行有一個整數T (1\leq T\leq 10)T(1≤T≤10), 表示測試資料的組數. 對于每組資料:
第一行輸入字元串SS。
第二行輸入一個整數kk。
      

輸出描述

對于每組資料，輸出符合要求的子串的個數。      

輸入樣例

2
abcabcabca
4
abcabcabcabc
3
      

輸出樣例

0
55      

//思路： 一個模拟題，從第一個字元一直周遊到最後一個，如果在前kk個字元間剛好有k個不相同的字元，那麼在此處就不用往後走了，後面的隻要逐個加上都是滿足題意的，然後再去掉前面的i個字元，看是否還滿足前kk個字元之間剛好有k個不同的字元，若滿足則kk不用往後走，直接加上相應的長度即可，若不滿足，那麼kk再往後走，直到找到滿足題意的要求後再停止，然後加上相應的後面的後面的長度。 按照這個一直全部周遊一遍後，所得即為所求。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 1000010
using namespace std;
char s[N];
int c[210];
int main()
{
	int t,k,i,j;
	scanf("%d",&t);
	while(t--)
	{		
		scanf("%s%d",s,&k);
		int len=strlen(s);
		ll ans=0;
		int cnt=0,kk=0;
		memset(c,0,sizeof(c));
		for(i=0;i<len;i++)
		{
			if(i)
			{
				c[s[i-1]]--;
				if(!c[s[i-1]])
					cnt--;
			}
			while(cnt<k&&kk<len)
			{
				if(!c[s[kk]])
					cnt++;
				c[s[kk++]]++;
			}
			if(cnt>=k)
				ans+=len-kk+1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}