Skip to content

1443: 小V的匹配作业

题目

题目描述

小V的作业有点简单,他不太想做,所以想请你来帮他做一下。题目是这样的,小V有一个数据库包含 n 个字符串,老师给了一些其他字符串用来询问,有 m 个,想让小V依次找到每个询问的字符串在数据库中“最接近的”字符串。评价两个字符串“最接近”的标准是:将两个字符串”对齐“(对齐的方式为在两个字符串中任意位置插入一些空格,使两个字符串长度相同),然后计算这种“对齐”方式的 cost 。cost 是对两个字符串每一个对应位置的 “分数” 求和,分数计算如下:

  1. 如果对应位置字符相同,分数为 0;
  2. 如果对应位置为两个非空格字符,且不相同,分数为 3;
  3. 如果对应位置有且仅有一个空格,分数为 2。

目标就是找到某种“对齐”方式,使得 cost 最小!对于老师给的每个字符串,你需要在数据库中找出与它最接近的那个字符串。为了减少小V的负担,老师只要求他算出这 m 个字符串中的每个在数据库中匹配之后,最小的 cost。

输入格式

第一行是一个整数 n

接下来 n 行是数据库中的 n 个字符串

下面一行是一个整数 m

接下来是要询问的 m 个字符串

输出格式

输出每个询问的最小 cost ,每行输出一个

样例输入

4 ABBC ACCA BBC ABCD 3 ABCC ACBC ACD

样例输出

3 3 2

数据范围

计算举例

ABCD 与 ACD 进行匹配:

ABCD

A-CD

cost = 2

30%的数据:字符串长度不超过 100;0 < n < = 50;0 < m <= 5

100%的数据:字符串长度不超过300; 0 < n < 100; 0 < m < 20

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!