題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5672

String

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1133Accepted Submission(s): 367

Problem Description There is a stringS.Sonly contain lower case English character.(10≤length(S)≤1,000,000)
How many substrings there are that contain at leastk(1≤k≤26)distinct characters?
Input There are multiple test cases. The first line of input contains an integerT(1≤T≤10)indicating the number of test cases. For each test case:

The first line contains stringS.
The second line contains a integerk(1≤k≤26).
Output For each test case, output the number of substrings that contain at leastkdictinct 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)個不同的字母？

解題思路：采用兩個指針，輪流更新左右邊界，同時累加答案。

注意：1、在更換頭指針的時候，需要考慮是否我用來記錄的num值可以減掉，因為如果兩個字符相同的話，在這個子串中不同字符的數目是不變的。

2、如果每更換一次頭指針，我就把i重新再來一次，就會超時。

詳見代碼。

#include 
#include 
#include 

using namespace std;

#define ll long long

const int N=1e6+9;
char ch[N];
int k;
int vis[300];

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%s%d",ch,&k);
        int len=strlen(ch);
        int head=0,num=0;
        ll ans=0;
        memset(vis,0,sizeof(vis));//vis是用來表示字符出現的次數，而不是標記是否出現過
        for (int i=0; i=k)//只要和至少的k相同時，就可以直接的計算出後面的有多少個
            {
                ans+=len-i;
                if (vis[ch[head]]==1)//判斷這個字符是不是只出現一次，如果是的話num--，否則num不變
                    num--;
                vis[ch[head]]--;
                head++;
                //memset(vis,0,sizeof(vis));
            }
        }
        printf ("%lld\n",ans);
    }
    return 0;
}