（尺取法）Codeforces 676C

原题链接：

http://codeforces.com/problemset/problem/676/C

题意：

有一串a和b组成的字符串，要求最多改k的字母的情况下，最长的相同子串。
例如k=2：abba->aaaa，k=3：aaabb->bbbbb

分析：

首先可以看出如果要最长的话，改的a或b一定是连续的k个a或b，因此只要计算连续的k个a或b夹在中间和两边的字母个数，当然包括改的字母。所以只要维护一个k大小的窗口，不停向右滑动，来计算出每个窗口的答案，取最大值。时间复杂度为O(n)。

代码：

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<set>
 6 #include<map>
 7 #include<algorithm>
 8 #include<string>
 9 #include<queue>
10 #include<cmath>
11 #include<stack>
12 #include<cctype>
13 #include<list>
14 
15 
16 #define ll long long
17 #define ull unsigned long long
18 
19 using namespace std;
20 
21 const int maxn=100010;
22 const int inf=1<<30;
23 
24 char str[maxn];
25 int a[maxn];//存a和b在原数组的位置，通过可以算出所需求的字母的个数
26 int b[maxn];
27 
28 int main()
29 {
30     //#define DEBUG
31 
32 #ifdef DEBUG
33     freopen("in.txt","r",stdin);
34     //freopen("out.txt","w",stdout);
35 #endif
36 
37     int n,k;
38     while(~scanf("%d%d",&n,&k)){
39         scanf("%s",str+1);
40         int an=0,bn=0;
41         for(int i=1;i<=n;i++){
42             if(str[i]=='a')a[++an]=i;
43             else b[++bn]=i;
44         }
45         a[0]=b[0]=0;//左右边界处理
46         a[an+1]=b[bn+1]=n+1;
47         if(k>=an||k>=bn){
48             printf("%d
",n);
49             continue;
50         }
51         int ans=1;
52         int res;
53         if(k<an){
54             res=a[k+1]-1;
55             ans=max(res,ans);
56             for(int i=2;i<=an-k+1;i++){
57                 res-=a[i-1]-a[i-2];//去掉前面一段
58                 res+=a[i+k]-a[i+k-1];//加上后面一段
59                 ans=max(res,ans);//更新
60             }
61         }
62         if(k<bn){
63             res=b[k+1]-1;
64             ans=max(res,ans);
65             for(int i=2;i<=bn-k+1;i++){
66                 res-=b[i-1]-b[i-2];
67                 res+=b[i+k]-b[i+k-1];
68                 ans=max(res,ans);
69             }
70         }
71         printf("%d
",ans);
72     }
73     return 0;
74 }