String 尺取法

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 char s[1000010];  
 6 int vis[300];
 7 int main()
 8 {
 9     int tt,k,ss,t;  //ss 表示低的指针 t代表高的指针
10     scanf("%d",&tt);
11     while(tt--)
12     {
13         scanf("%s",s);
14         scanf("%d",&k);
15         ss=0;t=0;
16         long long sum=0;
17         int num=0;
18         int len=strlen(s);
19         memset(vis,0,sizeof(vis));
20         for(;;)
21         {
22             while(t<len&&num<k)
23             {
24                 if(!vis[s[t]])
25                 {
26                     vis[s[t]]++;
27                     num++;
28                 }
29                 else
30                     vis[s[t]]++;
31                 if(num>=k)      //如果子串不同字符大于k的退出
32                     break;
33                 t++;
34             }
35             if(num<k)       //退出后一种是大于不同字符退出，一种是到了最后len的时候退出，如第二种，则结束。
36                 break;
37             sum+=len-t;
38             vis[s[ss]]--;
39             if(!vis[s[ss]])     
40             {
41                 t++;
42                 num--;
43             }
44             ss++;       //没找到一处，就使低指针加1；
45         }
46         printf("%lld
",sum);
47     }
48     return 0;
49 }
50             
51

View Code

有一个明显的性质：如果子串(i,j)包含了至少k个不同的字符，那么子串(i,k),(j<k<length)也包含了至少kkk个不同字符。

因此对于每一个左边界，只要找到最小的满足条件的右边界，就能在O(1)O(1)O(1)时间内统计完所有以这个左边界开始的符合条件的子串。

寻找这个右边界，是经典的追赶法（尺取法,双指针法）问题。维护两个指针（数组下标），轮流更新左右边界，同时累加答案即可。复杂度 O(length(S))