首页 > 试题广场 >

小美找朋友

[编程题]小美找朋友
  • 热度指数：2618 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

       小美将自己朋友的名字写在了一块，惊讶地发现她写出的那个字符串S有一个惊人的性质：一个人是小美的朋友当且仅当她/他的名字是那个字符串的子序列。现在小团想根据那个字符串判断一个人是不是小美的朋友。

       *子序列：一个字符串A是另外一个字符串B的子序列，当且仅当可以通过在B中删除若干个字符（也可能一个都不删），其他字符保留原来顺序，使得形成的新字符串B’与A串相等。例如，ABC是AABDDC的子序列，而ACB不是AABDDC的子序列。


输入描述:
第一行两个正整数n，m分别表示小美朋友字符串S的长度，以及小团想了解是不是小美朋友的那个人的名字字符串T的长度。
第二行长度为n且仅包含小写字母的字符串S
第三行长度为m且仅包含小写字母的字符串T


输出描述:
如果小团想了解的那个人不是小美的朋友(即，T不是S的子序列)，输出一行”No”,否则输出一行”Yes”，并在第二行将T对应到S中的位置之和输出出来(从1开始编号)，由于可能有多种对应方式，请输出最小的位置之和。请参见样例解释获取更详细说明
示例1

输入

6 3
aabddc
abc

输出

Yes
10

说明

对于样例1
S=aabddc T=abc，T中a可以与S中第1个字符a对应起来，b可以与S中第3个字符b对应起来，c可以与S中第6个字符c对应起来，这样一来就找到了一个S中的子序列(仅保留第1、3、6个字符形成的子序列)，使其与T相等。这种情况下，位置之和为1+3+6=10
还有一种方案，是S仅保留第2、3、6个字符形成的子序列abc,仍然满足与T相等的条件。但是位置之和为2+3+6=11，并不是位置之和最小的，因而输出第一种对应方案的位置之和：10
示例2

输入

6 3
aabddc
acb

输出

No

说明

对于样例2
可以保留S中的第1、3、6个字符，形成子序列abc，但于T串acb不相等，因为b、c位置并不对应。可以证明，没有任何一种取S子序列的方式，可以使得取出的子序列和T相等，因而输出No

备注:
对于30%的数据, max(n,m)<=20
对于60%的数据, max(n,m)<=2000
对于100%的数据, max(n,m)<=200000
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
18条回答 4544浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号