牛客网真题-90-字符串距离

双层for会超时 正确思路为扫描法
两种扫描方式，s1中字符扫描s2, s2的字符扫描s1，一般选择用小的扫描大的。然后用前缀和数组存储a的数量
对于s2的第i个元素 扫描是s1的坐标是【i,len(s1)-len(s2)+i】

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        long cnt = 0;
        int[] numA = new int[s1.length()];
        for(int i = 0; i < s1.length(); i++){
            numA[i] = (i - 1 >= 0 ? numA[i - 1] : 0) + (s1.charAt(i) == 'a' ? 1 : 0);
        }
//        System.out.println(Arrays.toString(numA));
        for(int i = 0; i < s2.length(); i++){
            //从i到r中a的数量
            int r = s1.length() - s2.length() + i;
            int a = numA[r] - (i - 1 >= 0 ? numA[i - 1] : 0);
            if(s2.charAt(i) == 'b'){
                cnt += a;
            }else{
                int b = r - i + 1 - a;//字符总数减去a的数量
                cnt += b;
            }
        }
        System.out.println(cnt);
    }
}