问题1710--GG的匹配串

1710: GG的匹配串

时间限制: 1 Sec  内存限制: 128 MB
提交: 121  解决: 44
[提交] [状态] [讨论版] [命题人:]
题目描述

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

输入

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

输出

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

样例输入 Copy
2
ATUUUUAC
2
ATACGTCT
6
样例输出 Copy
1
3