首页 > 试题广场 >

小美找朋友

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

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

       *子序列:一个字符串A是另外一个字符串B的子序列,当且仅当可以通过在B中删除若干个字符(也可能一个都不删),其他字符保留原来顺序,使得形成的新字符串B’A串相等。例如,ABCAABDDC的子序列,而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

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)