hdu 5672 String（BC——查找子串的个数 模拟）

题目链接：

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 (p.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;
}