首页 > 试题广场 >

小美找朋友

[编程题]小美找朋友
  • 热度指数：2649 时间限制：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
算法知识视频讲解
添加回答
李洞宾头像 李洞宾
一定要检查输出。。。我No输出成NO，检查了半个小时。。
发表于 2021-08-28 10:45:31 回复(5)
牛客630号头像 牛客630号
60%一直调不出来，结果用long long就解决了，好像美团好多题都这样。。。。 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n,m;
    cin>>n>>m;
    vector<char> s;
    vector<char> t;

    long long result=0;
    int index=0;
    int temp = n+1;
    while(temp--){
        char one = getchar();
        if(one !='\n')
            s.push_back(one);
    }
    temp = m+1;
    while(temp--){
        char one = getchar();
        if(one !='\n')
            t.push_back(one);
    }
    /*
    for(int i=0;i<s.size();i++){
        cout<<s[i];
    }
    cout<<endl;
    for(int i=0;i<t.size();i++){
        cout<<t[i];
    }*/
    for(int i=0;i<s.size();i++){
        //cout<<index;
        if(t[index]==s[i]){
            //cout<<t[index]<<"+"<<index;
            result=result+i+1;
            index++;
        }
        if(index==m)
            break;
    }
    if(index<m){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
    cout<<result<<endl;
    return 0;
}


发表于 2021-05-06 21:44:02 回复(3)
pein531头像 pein531
这性质有什么好惊人的，名字全写一起不就会这样吗
言归正传，从左往右遍历一遍S字符串就可以了，从T的第一个字符开始，在遍历S时检查当前字符是否与T的第一个字符相等。如果相等，T就跳到第二个字符，马上更新一下字符的位置之和，以保证和为最小；S接着向后遍历，直到与T的第二个字符相等，T再跳到下一个字符，并更新此时字符的位置之和……
S的遍历结束后，如果T中所有的字符都在S中找到了，即指针指到了T.length()，就输出Yes和位置之和；否则此时T字符串的指针应该还没有指到T.length()，输出No。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        String S = br.readLine().trim();
        String T = br.readLine().trim();
        int j = 0;
        long posSum = 0;
        for(int i = 0; i < n; i++){
            if(j < T.length() && S.charAt(i) == T.charAt(j)){
                j++;
                posSum += i + 1;
            }
        }
        if(j == T.length()){
            System.out.println("Yes");
            System.out.println(posSum);
        }else{
            System.out.println("No");
        }
    }
}


编辑于 2021-03-27 09:25:49 回复(12)
看星星呐头像 看星星呐 
m,n = map(int, input().split())
s = list(input())
t = list(input())
flag = 0
axis = []
for i in range(len(t)):
    for j in range(flag,len(s)):
        if t[i]==s[j]:
            flag = j+1
            axis.append(j+1)
            if i==len(t)-1:
                print('Yes')
                print(sum(axis))
            break
    else:print('No')

发表于 2021-09-01 09:51:43 回复(0)
JavaScript
是久头像 是久
js双指针 
 const [n,m]=readline().split(' ').map(Number)
    let s=readline()
    let t=readline()
   let a=0,b=0
    let r=0
    while(b!=m && a!=n){
        if(t.charAt(b)==s.charAt(a)){
            r+=a+1
             b++
            a++
        }else{
            a++
        }
    }
    if(b!=m){
        console.log('No')
    }else{
        console.log('Yes')
        console.log(r)
    }


发表于 2022-09-20 17:22:51 回复(0)
Java
离开有🐟的季节头像 离开有🐟的季节
DP,dp数组含义为：以indexI结尾和IndexJ为结尾的两个串相同，所需取的最小str1的序列和
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        String str1 = sc.next();
        String str2 = sc.next();
        long[][] dp = new long[m+1][n+1];
        dp[0][0] = 0;
        for(int i=1;i<=n;i++){
            dp[0][i] = Long.MAX_VALUE;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1) && dp[i-1][j-1]!= Long.MAX_VALUE){
                    dp[i][j] = Math.min(dp[i-1][j-1]+i,dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        if(dp[m][n]==Long.MAX_VALUE){
            System.out.println("No");
        }else{
            System.out.println("Yes");
            System.out.println(dp[m][n]);
        }

    }
}
发表于 2022-08-29 17:09:11 回复(1)
难受啊兄弟头像 难受啊兄弟
一直卡60%，看了评论区才知道要用long 
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        String s1 = sc.nextLine().trim();
        String s2 = sc.nextLine().trim();
        int count = 0;
        int lastEnd = 0;
        long res = 0;
        for (int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            for (int j = lastEnd; j < s1.length(); j++) {
                if (s1.charAt(j) == c) {
                    res += j + 1;
                    lastEnd = j + 1;
                    count++;
                    break;
                }
            }
        }

        if (count == s2.length()) {
            System.out.println("Yes");
            System.out.println(res);
        } else {
            System.out.println("No");
        }
    }
}


发表于 2022-08-26 20:10:21 回复(0)
immatur1ty头像 immatur1ty
这不给数据范围，sum会爆int你让我怎么查
发表于 2022-08-04 23:01:41 回复(0)
牛客304000217号头像 牛客304000217号

其实这道题好简单，自己想得好复杂，救命，用了动态规划做不出来，后面仔细想想才发现其实就是遍历而已。。。做题之前一定要好好思考再下手啊，好无语 
package main

import "fmt"

func main() {
	var M,N int
	var Mstr,Nstr string
	fmt.Scan(&M,&N,&Mstr,&Nstr)
	b,index:=0,0
	//var res string
	for i:=0;i<M;i++{
		if Mstr[i]==Nstr[index]&&index<N{

			index++
			b+=i+1
		}
	}
	if index==N{
		fmt.Println("Yes")
		fmt.Println(b)
	}else {
		fmt.Println("No")
	}
}



发表于 2022-05-25 23:40:17 回复(0)
前端HAN11头像 前端HAN11 
const rl = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});
let inputArr = [];//输入数组，用来保存输入
rl.on('line', function(line){
    inputArr.push(line);//将输入保存到inputArr数组中 例：得到['6 3', 'aabddc', 'abc']
}).on('close', function(){
    let [n, m] = inputArr[0].split(' ').map(Number);//获取n, m
    deal(n, m, inputArr[1], inputArr[2])//调用deal()函数，输出结果
})
function deal(n, m, s, t){
    let p = 0,
        q = 0,
        res = 0;
    while(p < n && q < m){
        if(s[p] === t[q]){
            res += p + 1;
            p++;
            q++;
        }else{
            p++;
        }
    }
    if(q === m){
        console.log('Yes');
        console.log(res);
    }else{
        console.log('No');
    }
}
发表于 2021-08-19 15:59:51 回复(0)
刷完这题我就去睡觉头像 刷完这题我就去睡觉
双指针，注意开ll 
/**
 *      author:刷完这题就去睡觉
 *      created:
**/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    if(n<m){
        cout<<"No"<<endl;
        return 0;
    }
    string s,t;
    cin>>s;
    cin>>t;
    ll l=0,r=0;
    ll ans=0;
    while(l<n&&r<m){
        if(s[l]==t[r]){
            ans+=(l+1);
            l++;
            r++;
        }else{
            l++;
        }
    }
    if(r==m){
        cout<<"Yes"<<endl;
        cout<<ans<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

发表于 2021-08-16 19:45:59 回复(0)
有一个地方.头像 有一个地方.
双指针 
n, m = map(int, input().split())
s = input()
t = input()
p1, p2 = 0, 0
ans = 0
while p1 < n and p2 < m:
    if s[p1] == t[p2]:
        ans += (p1 + 1)
        p1 += 1
        p2 += 1
    else:
        p1 += 1
if p2 == m:
    print("YES")
    print(ans)
else:
    print('NO')


发表于 2021-07-09 17:12:48 回复(0)
Christine201909291558974头像 Christine201909291558974
双指针，一个指针访问原字符串，一个访问目标字符串，一遍AC~ 
n,m = map(int,input().split())
string = input()
target = input()
index_num = 0
i,j = 0,0
while i<n and j<m:
    if string[i]==target[j]:
        j+=1
        index_num+=i+1
    i+=1
if j==m:
    print("Yes")
    print(index_num)
else:
    print("No")

发表于 2021-05-15 09:56:02 回复(0)
许愿给我来一个offer呀头像 许愿给我来一个offer呀
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String d = sc.nextLine();
         String s= sc.nextLine();
        String z = sc.nextLine();
        int start = 0;
        long result =0;
        for(int i =0;i<s.length();i++){
            if(s.charAt(i)==z.charAt(start)){
                result +=i+1;
                start++;
            }
        }
        if(start<m){
            System.out.print("No");
        }else{
            System.out.println("Yes");
            System.out.println(result);
        }
      }
}
发表于 2021-05-06 10:50:22 回复(0)
云瓞头像 云瓞
双指针判断子序列 
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String S = sc.next();
        String T = sc.next();
        print(S,T);
    }
    public static void print(String S,String T){
        if(S.length()<T.length()){
            System.out.println("No");
            return;
        }
        long res = 0;
        int i = 0;
        int j = 0;
        while(i<T.length() && j<S.length()){
            if(T.charAt(i)==S.charAt(j)){
                i++;
                res+=j+1;
            }
            j++;
        }
        if( i == T.length()){
            System.out.println("Yes");
            System.out.print(res);
        }
        else{
            System.out.println("No");
        }

    }
}

发表于 2021-05-05 20:54:13 回复(0)
牛客默克尔号头像 牛客默克尔号
自己做的，做完一看评论区，大家的方法都比我的简单，自愧不如啊哈哈哈，继续干！ 
m,n=[int(i) for i in input().split()]
l=input()
ll=input()
sum=0
a=-1
b=len(l)-1
if len(ll)>len(l):
    print('No')
else:
    for i in ll:
        p=0
        for j in range(a+1,b+1):
            if i==l[j]:
                a=j
                sum+=a+1
                p=1
                break
        if p==0:
            print('No')
            break
    if p==1:
        print('Yes')
        print(sum)


发表于 2021-04-17 21:46:58 回复(0)
牛客109286625号头像 牛客109286625号
你要干什么，不能出个明确的题目吗，题目看着云里雾里的
发表于 2021-04-08 20:54:00 回复(0)
31415926535x头像 31415926535x
序列自动姬（适合多数据）或者双指针（注意会爆int
发表于 2021-04-06 09:21:09 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

相关试题

小美找朋友

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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