//参考大佬的意见     public static void main(String[] args) {              Scanner sin=new Scanner(System.in);         while (sin.hasNext()) {                         String s=sin.nextLine();//母串             String t=sin.nextLine();//字串          long startTime=System.currentTimeMillis();   //获取开始时间             if (t.length() > s.length() || s.length() == 0 || t.length() == 0) {             } else {                 char[] S = s.toCharArray();                 char[] T = t.toCharArray();                 int sum = 0; //输出两个字符串的距离                 int count_b = 0, count_a = 0;                 int lenS = S.length, lenT = T.length;                 for (int i = 0; i <= lenS - lenT; i++) {                     count_a = S[i] == 'a' ? count_a + 1 : count_a;                     count_b = S[i] == 'b' ? count_b + 1 : count_b;                     //其中,count_b 是S[i]...S[i+|S|-|T|]中的b字符的数量                 }                   for (int i = 0; i + lenS - lenT < lenS; i++) {                     //1.怎么计算T[i]对答案的贡献                     //  T[i]会与S[i]...S[i+|S|-|T|]比较,i取0...|T|-1                     //  因为是计算距离,并且字符只会是'a'或者'b',所以T[i]对答案的贡献是                     sum += T[i] == 'a' ? count_b : count_a;                     //2.T[i+1]对答案的贡献与T[i]的递推关系                     //  T[i+1]时只需要在T[i]统计的基础上,考虑减掉S[i],加上S[i+1+|S|-|T|]                     if (S[i] == 'a') {                         --count_a;                     } else {                         --count_b;                     }                     //i取lenT-1时,S[]会超范围                     if (i + lenS - lenT + 1 == lenS) {                     } else {                         if (S[i + lenS - lenT + 1] == 'a') {                             ++count_a;                         } else {                             ++count_b;                         }                     }                 }                 System.out.println(sum);                 long endTime = System.currentTimeMillis(); //获取结束时间                 System.out.println("程序运行时间: " + (endTime - startTime) + "ms");             }         }     }
点赞 2

相关推荐

点赞 评论 收藏
分享
Volatiled:对方撤回了啥呀?
点赞 评论 收藏
分享
牛客网
牛客企业服务