Ural1517最长公共子序列

作者：摩擦摩擦魔鬼的步伐 | 来源：互联网 | 2023-08-26 16:27

DescriptionBackgroundBeforeAlbanianpeoplecouldbearwiththefreedomofspeech(thisstory

Description

Background

Before Albanian people could bear with the freedom of speech (this story is fully described in the problem
"Freedom of speech"), another freedom - the freedom of choice - came down on them. In the near future, the inhabitants will have to face the first democratic Presidential election
in the history of their country.

Outstanding Albanian politicians liberal Mohammed Tahir-ogly and his old rival conservative Ahmed Kasym-bey declared their intention to compete for the high post.

Problem

According to democratic traditions, both candidates entertain with digging dirt upon each other to the cheers of their voters‘ approval. When occasion offers, each candidate makes an election speech, which is devoted to blaming
his opponent for corruption, disrespect for the elders and terrorism affiliation. As a result the speeches of Mohammed and Ahmed have become nearly the same, and now it does not matter for the voters for whom to vote.

The third candidate, a chairman of Albanian socialist party comrade Ktulhu wants to make use of this situation. He has been lazy to write his own election speech, but noticed, that some fragments of the speeches of Mr. Tahir-ogly
and Mr. Kasym-bey are completely identical. Then Mr. Ktulhu decided to take the longest identical fragment and use it as his election speech.

Input

The first line contains the integer number
N (1 ≤ N ≤ 100000). The second line contains the speech of Mr. Tahir-ogly. The third line contains the speech of Mr. Kasym-bey. Each speech consists of
N capital latin letters.

Output

You should output the speech of Mr. Ktulhu. If the problem has several solutions, you should output any of them.

Sample Input

input	output
28 VOTEFORTHEGREATALBANIAFORYOU CHOOSETHEGREATALBANIANFUTURE	THEGREATALBANIA

题意：求最长公共子序列，要求输出，

遇上一题一样，加一点记录就行。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-28 18:11:33
File Name :4.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=2000200;
int height[maxn],sa[maxn],rank[maxn],c[maxn],t1[maxn],t2[maxn];
void da(int *str,int n,int m)
{
int i,j,k,p,*x=t1,*y=t2;
for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1)
{
p=0;
for(i=n-k;i for(i=0;i=k)y[p++]=sa[i]-k;
for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=1;x[sa[0]]=0;
for(i=1;i x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
if(p>=n)break;
m=p;
}
}
void calheight(int *str,int n)
{
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i {
if(k)k--;
j=sa[rank[i]-1];
while(str[i+k]==str[j+k])k++;
height[rank[i]]=k;
}
}
int str[maxn];
char ss[maxn];
int Log[maxn];
int best[23][maxn];
void init(int n)
{
int i,j;
Log[0]=-1;
for(i=1;i<=n;i++)
Log[i]=(i&(i-1))?Log[i-1]:Log[i-1]+1;
for(i=1;i<=n;i++)best[0][i]=height[i];
for(i=1;i<=Log[n];i++)
for(j=1;j<=n;j++)
best[i][j]=min(best[i-1][j],best[i-1][j+(1<<(i-1))]);
}
int lcp(int a,int b)
{
a=rank[a];
b=rank[b];
if(a>b)swap(a,b);
a++;
int t=Log[b-a+1];
return min(best[t][a],best[t][b-(1<}
char s1[maxn],s2[maxn];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n;
while(~scanf("%d",&m))
{
scanf("%s%s",s1,s2);
int l1=strlen(s1);
int l2=strlen(s2);
int len=0;
for(i=0;i str[len++]=1;
for(i=0;i str[len]=0;
da(str,len+1,300);
calheight(str,len);
// printf("sa:");for(i=0;i<=len;i++)printf("%d ",sa[i]);puts("");
// printf("rank:");for(i=0;i<=len;i++)printf("%d ",rank[i]);puts("");
// printf("height:");for(i=0;i<=len;i++)printf("%d ",height[i]);puts("");
int be,ans=0;
for(i=1;i<=len;i++)
{
if((sa[i]l1)||(sa[i]>l1&&sa[i-1] if(ans }
for(i=be;i puts("");
}
return 0;
}

推荐阅读

io
Android开发笔记：使用Picasso加载网络图片等比例缩放

在Android开发中，使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法，并提供了具体的代码实现。通过获取图片的宽高，计算目标宽度和高度，并创建新图实现等比例缩放。 ... [详细]

蜡笔小新 2023-12-14 17:34:00
io
基于layUI的图片上传前预览功能的2种实现方式

本文介绍了基于layUI的图片上传前预览功能的两种实现方式：一种是使用blob+FileReader，另一种是使用layUI自带的参数。通过选择文件后点击文件名，在页面中间弹窗内预览图片。其中，layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块，并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]

蜡笔小新 2023-12-14 17:06:58
main
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
main
Alink回归预测的不完善问题及期待

本文讨论了Alink回归预测的不完善问题，指出目前主要针对Python做案例，对其他语言支持不足。同时介绍了pom.xml文件的基本结构和使用方法，以及Maven的相关知识。最后，对Alink回归预测的未来发展提出了期待。 ... [详细]

蜡笔小新 2023-12-14 14:25:33
main
C#生成随机数的三种方法及其问题分析

本文介绍了C#中生成随机数的三种方法，并分析了其中存在的问题。首先介绍了使用Random类生成随机数的默认方法，但在高并发情况下可能会出现重复的情况。接着通过循环生成了一系列随机数，进一步突显了这个问题。文章指出，随机数生成在任何编程语言中都是必备的功能，但Random类生成的随机数并不可靠。最后，提出了需要寻找其他可靠的随机数生成方法的建议。 ... [详细]

蜡笔小新 2023-12-14 14:15:30
main
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
main
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
string
Mac OS 升级到11.2.2 Eclipse打不开了，报错Failed to create the Java Virtual Machine

本文介绍了在Mac OS升级到11.2.2版本后，使用Eclipse打开时出现报错Failed to create the Java Virtual Machine的问题，并提供了解决方法。 ... [详细]

蜡笔小新 2023-12-14 12:01:13
string
测试人的性格，点火让他着急，考验婚姻问题的善意玩人

本文讲述了作者通过点火测试男友的性格和承受能力，以考验婚姻问题。作者故意不安慰男友并再次点火，观察他的反应。这个行为是善意的玩人，旨在了解男友的性格和避免婚姻问题。 ... [详细]

蜡笔小新 2023-12-14 09:10:09
数组
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
io
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
cookie
Webmin远程命令执行漏洞复现及防护方法

本文介绍了Webmin远程命令执行漏洞CVE-2019-15107的漏洞详情和复现方法，同时提供了防护方法。漏洞存在于Webmin的找回密码页面中，攻击者无需权限即可注入命令并执行任意系统命令。文章还提供了相关参考链接和搭建靶场的步骤。此外，还指出了参考链接中的数据包不准确的问题，并解释了漏洞触发的条件。最后，给出了防护方法以避免受到该漏洞的攻击。 ... [详细]

蜡笔小新 2023-12-13 16:14:53
main
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
main
Java验证码——kaptcha的使用配置及样式

本文介绍了如何使用kaptcha库来实现Java验证码的配置和样式设置，包括pom.xml的依赖配置和web.xml中servlet的配置。 ... [详细]

蜡笔小新 2023-12-13 13:58:25
main
Java实战之电影在线观看系统的实现

本文介绍了Java实战之电影在线观看系统的实现过程。首先对项目进行了简述，然后展示了系统的效果图。接着介绍了系统的核心代码，包括后台用户管理控制器、电影管理控制器和前台电影控制器。最后对项目的环境配置和使用的技术进行了说明，包括JSP、Spring、SpringMVC、MyBatis、html、css、JavaScript、JQuery、Ajax、layui和maven等。 ... [详细]

蜡笔小新 2023-12-14 15:52:03

摩擦摩擦魔鬼的步伐

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

Tags | 热门标签

RankList | 热门文章