BestCoder Round\# 81 (div. 2) - String (척 취 법)

String  
 Accepts: 84
 
 Submissions: 373
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 65536/65536 K (Java/Others)
문제 설명

    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

String
        ：    (i,j)(i,j)     kk      ，    (i,k),(j < k < length)(i,k),(j<k<length)      kk     。
          ，               ，   O(1)O(1)                        。
       ，       （   ,    ）  。      （    ），        ，        。    O(length(S))O(length(S))。

AC  ：

#include<iostream>
#include<functional>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define QWQ ios::sync_with_stdio(0)
#define inf 0x3f3f3f3f
typedef unsigned long long LL;
typedef  long long ll;

const int T = 1000000+50;
const int mod = 1000000007;
const int mo = 772002+233;

char s[T];
int vis[T];

int main()
{

#ifdef zsc
    freopen("input.txt","r",stdin);
#endif

	int n,m,i,j,k;
	~scanf("%d",&n);
	while(n--)
	{
		memset(vis,0,sizeof(vis));
		scanf("%s",s+1);
		scanf("%d",&m);
		int cnt = 0,cur=0;//         ，      
		ll ans = 0;//   
		for(i=1;s[i];++i){
			int t = s[i]-'a';
			if(!vis[t]++)cnt++;//       
			while(cnt>=m&&cur<i)//          
			if(cur++,!(--vis[s[cur]-'a']))cnt--;//      ，       
			ans += cur;//    【1，len（s）】   ，           cur   
		}
		printf("%lld
",ans);
	}
	
    return 0;
}