关注
//参考大佬的意见
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
相关推荐
牛客热帖
更多
正在热议
更多
# 我的求职总结 #
12286次浏览 225人参与
# 辞职之后最想做的一件事 #
7985次浏览 87人参与
# 毕业季,给职场新人一些建议 #
11645次浏览 216人参与
# 选offer应该考虑哪些因素 #
9875次浏览 135人参与
# 我的实习日记 #
2417486次浏览 25273人参与
# 工作后会跟朋友渐行渐远吗 #
20514次浏览 159人参与
# 你小时候最想从事什么职业 #
90119次浏览 1690人参与
# 你想留在一线还是回老家? #
36344次浏览 439人参与
# 薪资爆料 #
102013次浏览 1039人参与
# 毕业后不工作的日子里我在做什么 #
167758次浏览 1484人参与
# 设计人如何选offer #
108025次浏览 707人参与
# 生物制药/化工校招攻略 #
42632次浏览 282人参与
# 比亚迪求职进展汇总 #
703376次浏览 3060人参与
# 第一份工作应该只看薪资吗 #
136869次浏览 1438人参与
# 你们公司哪个部门最累? #
14371次浏览 123人参与
# 你们的毕业论文什么进度了 #
1013956次浏览 9513人参与
# 秋招想进国企该如何准备 #
56673次浏览 363人参与
# 招聘要求与实际实习内容不符怎么办 #
98175次浏览 718人参与
# 工作中的卑微时刻 #
8770次浏览 54人参与
# 大学最后一个寒假,我想…… #
35464次浏览 454人参与