hdu Boring count（BestCode round #11）

Boring count

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 360 Accepted Submission(s): 140


Problem Description 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.
Input 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
Output For each case, output a line contains the answer.
Sample Input

3
abc
1
abcabc
1
abcabc
2

Sample Output

6
15
21

官方題解：

枚舉字符串下標i，每次計算以i為結尾的符合條件的最長串。那麼以i為結尾的符合條件子串個數就是最長串的長度。求和即可。
計算以i為結尾的符合條件的最長串兩種方法：
1.維護一個起點下標startPos，初始為1。如果當前為i，那麼cnt[str[i]]++，如果大於k的話，就while( str[startPos] != str[i+1] ) cnt[str[startPos]]--, startPos++; 每次都保證 startPos~i區間每個字母個數都不超過k個。ans += ( i-startPos+1 )。 時間復雜度O(n)
2.預處理出所有字母的前綴和。然後通過二分找出以i為結尾的符合條件的最長串的左邊界。時間復雜度O(nlogn)，寫的不夠好的可能超時。

代碼：

#include 
#include 
#include 
#include 
using namespace std;
int a[30];
char s[101000];
int main()
{
    int t,k,n;
    scanf("%d",&t);
    while(t--)
    {
         memset(s,0,sizeof(s));
         memset(a,0,sizeof(a));
        scanf("%s",s);
        n=strlen(s);
        scanf("%d",&k);
        long long ans=0;
        int start=0;
        for(int i=0;ik)
            {
                while(s[start]!=s[i])
                {
                    a[s[start]-'a']--;
                    start++;
                }
                a[s[start]-'a']--;
                    start++;
            }
            ans+=(i-start+1);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}