HDU_5056

描述

You are given a string S consisting of lowercase letters, and your task is counting the number of substring that the number of each lowercase letter in the substring is no more than K.

输入格式

In the first line there is an integer T , indicates the number of test cases.
For each case, the first line contains a string which only consist of lowercase letters. The second line contains an integer K.

[Technical Specification]
1<=T<= 100
1 <= the length of S <= 100000
1 <= K <= 100000

输出格式

For each case, output a line contains the answer.

样例

输入

3
abc
1
abcabc
1
abcabc
2

输出

6
15
21

思路

i,j表示最大不冲突字串的首和尾。
用26个队列来存26个字母的位置，当某个队列的size大于k时，明显冲突。计算i-j之间的子串的个数。要注意算重的部分，要减去。
i更新为对应队列里front的值。特别注意的是，位置在old_i和new_i之间的字母的队列要pop掉，这个BUG卡了我两个小时，OMG…………
代码很简约，也比较易懂。

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long fun(long long i,long long j){
    if(j>=i)return (1+j-i+1)*(j-i+1)/2;
    else return 0;
}
int main(){
    int T;cin>>T;
    while(T--){ 
        queue <long long > qu[26];char s[100005];
        long long ans=0,i=0,j=0,k,len;
        scanf("%s%lld",s,&k);len=strlen(s);
        for(;j<len;j++){
            if(qu[s[j]-'a'].size()+1<=k){
                qu[s[j]-'a'].push(j);
            }
            else{
                ans+=fun(i,j-1);long long tmp=qu[s[j]-'a'].front()+1;
                for(long long p=i;p<tmp;p++)qu[s[p]-'a'].pop();/*之前少了这行代码，一直wa*/
                i=tmp;
                qu[s[j]-'a'].push(j);
                ans-=fun(i,j-1);/*算重的部分要减去*/
            }
        }
        ans+=fun(i,j-1);
        printf("%lld\n",ans);
    }
    return 0;
}