首页 > 试题广场 >

字符串距离

[编程题]字符串距离

热度指数：2671 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出两个相同长度的由字符 a 和 b 构成的字符串，定义它们的距离为对应位置不同的字符的数量。如串 ”aab” 与串 ”aba” 的距离为 2 ;串 ”ba” 与串 ”aa” 的距离为 1 ;串 ”baa” 和串 ”baa” 的距离为 0 。下面给出两个字符串 S 与 T ，其中 S 的长度不小于 T 的长度。我们用 |S| 代表 S 的长度，|T| 代表 T 的长度，那么在 S 中一共有 |S|-|T|+1 个与 T 长度相同的子串，现在你需要计算 T 串与这些 |S|-|T|+1 个子串的距离的和。

注意：子串指字符串中一段连续的串

数据范围： $1 \le |T|，|S| \le 10^5 \$ ，字符串中仅包含 'a' ， 'b'

输入描述:

第一行包含一个字符串 S。

第二行包含一个字符串 T。
S和T均由字符a和b组成。

输出描述:

输出对应的答案。

示例1

输入

aab
aba

输出

示例2

输入

aaabb
bab

输出

说明

在样例 2 中，”aaa”与”bab”的距离为 2，”aab”与”bab”的距离为 1，”abb”与”bab”的距离为 2，
所以最后答案为 5。

算法知识视频讲解

17c89

发表于 2024-02-25 12:10:54

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

laglangyue

发表于 2020-06-25 20:57:47

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