小美将自己朋友的名字写在了一块，惊讶地发现她写出的那个字符串S有一个惊人的性质：一个人是小美的朋友当且仅当她/他的名字是那个字符串的子序列。现在小团想根据那个字符串判断一个人是不是小美的朋友。
*子序列：一个字符串A是另外一个字符串B的子序列，当且仅当可以通过在B中删除若干个字符（也可能一个都不删），其他字符保留原来顺序，使得形成的新字符串B’与A串相等。例如，ABC是AABDDC的子序列，而ACB不是AABDDC的子序列。
[编程题]小美找朋友
- 热度指数：2618 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行两个正整数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
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)
这性质有什么好惊人的，名字全写一起不就会这样吗
言归正传，从左往右遍历一遍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)
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)
其实这道题好简单，自己想得好复杂，救命，用了动态规划做不出来，后面仔细想想才发现其实就是遍历而已。。。做题之前一定要好好思考再下手啊，好无语
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)
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)
双指针，一个指针访问原字符串，一个访问目标字符串，一遍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)
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);
}
}
}
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)
问题信息
通过挑战的用户
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
