HDU1503：高级水果的最长公共子序列路径分析

作者：关圣钊 | 来源：互联网 | 2024-10-28 08:09

题目描述：21世纪水果公司专注于开发新型水果品种。本研究通过高级水果的最长公共子序列路径分析，探讨了不同水果品种之间的遗传关系和进化路径，为新品种的培育提供了科学依据。该方法不仅提高了品种鉴定的准确性，还为遗传多样性研究提供了新的视角。

Problem Description

The company "21st Century Fruits" has specialized in creating new sorts of fruits by transferring genes from one fruit into the genome of another one. Most times this method doesn't work, but sometimes, in very rare cases, a new fruit emerges that tastes like a mixture between both of them.
A big topic of discussion inside the company is "How should the new creations be called?" A mixture between an apple and a pear could be called an apple-pear, of course, but this doesn't sound very interesting. The boss finally decides to use the shortest string that contains both names of the original fruits as sub-strings as the new name. For instance, "applear" contains "apple" and "pear" (APPLEar and apPlEAR), and there is no shorter string that has the same property.

A combination of a cranberry and a boysenberry would therefore be called a "boysecranberry" or a "craboysenberry", for example.

Your job is to write a program that computes such a shortest name for a combination of two given fruits. Your algorithm should be efficient, otherwise it is unlikely that it will execute in the alloted time for long fruit names.

Input

Each line of the input contains two strings that represent the names of the fruits that should be combined. All names have a maximum length of 100 and only consist of alphabetic characters.

Input is terminated by end of file.

Output

For each test case, output the shortest name of the resulting fruit on one line. If more than one shortest name is possible, any one is acceptable.

Sample Input

apple peach

ananas banana

pear peach

Sample Output

appleach

bananas

pearch

题意：将两个字符串结合起来，他们的公共子串只输出一次

思路：LCS处理以后逆序输出标记路径的方法值得学习，如果字母不相同的话就看当前i和j谁能影响前面的公共字母个数。

#include 
#include 
#include 
#include
#include
#define ll long long int
#define M 6
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int dp[107][107];
int mark[107][107]; //0表示为公共字母  1表示i-1没有贡献  -1表示j-1没有贡献 
string s,t;
void output(int i,int j){ //打印路径 
//    cout<
    if(i==0||j==0){
        if(i==0)
            for(int k=0;k)
                cout<<t[k];
        else
            for(int k=0;k)
                cout<<s[k];
        return ;
    } 
    if(mark[i][j]==0){
        output(i-1,j-1);
        cout<1];
    }else if(mark[i][j]==-1){
        output(i-1,j);
        cout<1];
    }else{
        output(i,j-1);
        cout<1];
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>s>>t){
        memset(dp,0,sizeof(dp));
        memset(mark,0,sizeof(mark));
        int len1,len2;
        len1=s.length(); len2=t.length();
        for(int i=1;i<=len1;i++)
            for(int j=1;j<=len2;j++){
                if(s[i-1]==t[j-1]){  
                    dp[i][j]=dp[i-1][j-1]+1;
                    mark[i][j]=0;
                }else if(dp[i][j-1]>dp[i-1][j]){
                    dp[i][j]=dp[i][j-1];
                    mark[i][j]=1;
                }else{
                    dp[i][j]=dp[i-1][j];
                    mark[i][j]=-1;
                }
            }
        output(len1,len2);
        cout<<endl;
    }
    return 0;
}

推荐阅读

int
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
int
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
int
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
int
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
int
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
int
java编写的简易计算器

主要用了2个类来实现的，话不多说，直接看运行结果，然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]

蜡笔小新 2024-12-27 18:18:10
int
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
include
HTML Attribute Naming Conventions for Fast Components

This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]

蜡笔小新 2024-12-26 19:13:45
int
Java 中 Writer flush()方法，示例

Java 中 Writer flush()方法，示例 ... [详细]

蜡笔小新 2024-12-28 06:41:52
int
火星商店问题：线段树分治与持久化Trie树的应用

本题涉及编号为1至n的火星商店，每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品，以及查询某段时间内某些商店中所有商品（含永久商品）与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]

蜡笔小新 2024-12-27 21:23:11
int
深入解析 MVC 源码：ParameterDescriptor 与 Action 方法参数绑定

在前两篇文章中，我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象，分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor，即用于描述 Action 方法参数的对象，并详细介绍其工作原理。 ... [详细]

蜡笔小新 2024-12-27 15:26:10
int
Akka BackoffSupervisor的深入解析与实践

本文详细介绍了Akka中的BackoffSupervisor机制，探讨其在处理持久化失败和Actor重启时的应用。通过具体示例，展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]

蜡笔小新 2024-12-27 15:04:09
int
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14
int
C语言实现小写金额转换为大写金额

在金融和会计领域，准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据，还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法，确保数据的标准化和规范化。 ... [详细]

蜡笔小新 2024-12-27 12:39:06
int
Unity 客户端框架设计：UI管理系统的构建

本文详细介绍了如何构建一个高效的UI管理系统，集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑，实现功能逻辑分散化和代码复用，支持多人协作开发。 ... [详细]

蜡笔小新 2024-12-27 10:28:40

关圣钊

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章