广工校赛——GG的匹配串

Description

2015年广东工业大学ACM校赛要来~(≧▽≦)/~辣辣辣，作为校赛的出题人之一，GG想出了一道水题来考考大家。相信小伙伴们都学过字符串匹配，于是字符串匹配的水题就诞生辣！GG给出了一段长度为N的大写字母序列，现在他要你修改这一段字母序列，使得这段字母序列上最前面的K个字母组成的序列与最后面的K个字母组成的序列一一匹配。 
 
例如对于序列“ATUUUUAC”和K = 2，可以通过将第二个字母修改为“C”,使得最前面的两个字母与最后面的两个字母都为“AC”，当然 还存在其他的修改方法，现在GG要求你求出要使字符串匹配至少需要修改多少个字母。

Input

有T组数据输入。（T <= 100） 
每组数据只有两行，第一行为一个字符串，第二行为一个正整数K，字符串的长度不会超过1000，且至少为1。（1 <= K <= N）。

Output

对于每组数据输出至少需要修改的字母数量

Sample Input

2 ATUUUUAC 2 ATACGTCT 6

Sample Output

1 3

HINT

大意：题目意思一直理解错，应该为就是一串，而且是修改的总次数，不是字母修改的数量- -||语文有待提升

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int ans;
char ch[1100];
int arr[26];
int T,k,n;
int f(int x)
{
    memset(arr,0,sizeof(arr));
    int re = 0;
    int r= 0;
    while( x < n){
            r++;
           arr[ch[x]-'A']++;
           x+=n-k;
    }
    for(int i = 0; i < 26; i++)
        re = max(re,arr[i]);
    return r-re;
}
int main()
{
    scanf("%d",&T);
    while(T--){
            scanf("%s%d",ch,&k);
           n = strlen(ch);
        int ans = 0;
        for(int i = 0 ; i < k && i < n - k; i++)
            ans += f(i);
        printf("%d
",ans);
    }
    return 0;
}