题目地址：http://hihocoder.com/problemset/problem/1052
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi和小Ho正在进行一项基因工程实验。他们要修改一段长度为N的DNA序列，使得这段DNA上最前面的K个碱基组成的序列与最后面的K个碱基组成的序列完全一致。
例如对于序列”ATCGATAC”和K=2,可以通过将第二个碱基修改为”C”使得最前面2个碱基与最后面两个碱基都为”AC”。当然还存在其他修改方法，例如将最后一个碱基改为”T”，或者直接将最前面两个和最后面两个碱基都修改为”GG”。
小Hi和小Ho希望知道在所有方法中，修改碱基最少的方法需要修改多少个碱基。
输入
第一行包含一个整数T(1 <= T <= 10)，代表测试数据的数量。
每组测试数据包含2行，第一行是一个由”ATCG”4个大写字母组成的长度为N(1 <= N <= 1000)的字符串。第二行是一个整数K(1 <= K <= N)。
输出
对于每组数据输出最少需要修改的碱基数量。
样例输入
2
ATCGATAC
2
ATACGTCT
6
样例输出
1
3
Java代码如下：
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in=new Scanner(System.in);int t=in.nextInt();while(t-->0){StringBuffer s=new StringBuffer(in.next());int k=in.nextInt();int count=0;int[] vis=new int[s.length()+3];for(int i=0;i<k;i++){if(vis[i]==0){int[] mk=new int[4];int max=0;for(int temp=0;temp+i-(s.length()-k)<k&&vis[temp+i]==0;temp+=(s.length()-k)){vis[temp+i]=1;switch (s.charAt(temp+i)) {case 'A': mk[0]++;break;case 'G': mk[1]++;break;case 'C': mk[2]++;break;case 'T': mk[3]++;break;}}for(int j=0;j<4;j++){if(mk[j]>max){max=mk[j];}}count+=mk[0]+mk[1]+mk[2]+mk[3]-max;}}System.out.println(count);}}}思路：有两种情况：
一种是左右两部分没有重叠的部分，直接比对即可。
还有一种情况比较复杂，就是左右部分有重叠，这种情况应该递归找到每组应该相等的位置，找出他们中哪个字母最多，把不是这个字母的数量记录下来，当前k个位置都经过判断了，就可以输出了。
如图所示， 左部分的标号为i的位置对应右部分标号为l-k+i的位置，即 i<–>l-l+i 但是，这个l-k+i也可能在左部分，把左边的i替换成l-k+i ,得到对应的位置2l-2k+i,这样一直递归下去，直到得到的右部x(l-k)+i不属于左部（>= k）为止。
建入一个visit数组用来判断该位置是否判断过，如果判断了就不用再判断了。