URAL1517后缀数据+最长公共前缀LCP

作者：ahao123 | 来源：互联网 | 2023-10-11 11:58

RE好久，靠，原来rank等数组得加倍了……晕……理解了后缀数组，不过最长公共前缀还没太理解，先用模板解决问题先吧……#include#include#include

RE好久，靠，原来rank等数组得加倍了……晕……

理解了后缀数组，不过最长公共前缀还没太理解，先用模板解决问题先吧……

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 400005
#define MN 2005
#define INF 100004
#define eps 1e-7
using namespace std;
typedef long long ll;
void radix(int *str,int *a,int *b,int n,int m)
{
static int count[MM];
mem(count,0);
for(int i=0;i for(int i=1;i<=m;i++) count[i]+=count[i-1];
for(int i=n-1;i>=0;i--) b[--count[str[a[i]]]]=a[i];
}
void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa
{
static int rank[MM],a[MM],b[MM];
for(int i=0;i radix(str,rank,sa,n,m);
rank[sa[0]]=0;
for(int i=1;i rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
for(int i=0;1< {
for(int j=0;j {
a[j]=rank[j]+1;
b[j]=j+(1<=n?0:rank[j+(1< sa[j]=j;
}
radix(b,sa,rank,n,n);
radix(a,rank,sa,n,n);
rank[sa[0]]=0;
for(int j=1;j rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
}
}
void calcHeight(int *str,int *sa,int *h,int n) //求出最长公共前缀数组h
{
static int rank[MM];
int k=0;
h[0]=0;
for(int i=0;i for(int i=0;i {
k=k==0?0:k-1;
if(rank[i])
while(str[i+k]==str[sa[rank[i]-1]+k]) k++;
else k=0;
h[rank[i]]=k;
}
}
void work(string a,string b) //求出最长公共子串
{
static int s[MM],sa[MM],h[MM];
static string str;
str=a+"#"+b;
int k=0,len=str.length();
copy(str.begin(),str.end(),s);
suffix(s,sa,len,len+256);
calcHeight(s,sa,h,len);
int ans=0,pos;
for(int i=1;i if(h[i]>ans&&(sa[i-1] ans=h[i],pos=sa[i];
if(ans==0) puts("Not Found");
else cout<}
int main()
{
int n;
string a,b;
cin>>n>>a>>b;
work(a,b);
return 0;
}

URAL 1517 后缀数据+最长公共前缀LCP,布布扣,bubuko.com

推荐阅读

string
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
string
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

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

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

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

蜡笔小新 2023-12-14 13:11:00
match
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
text
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
text
java 线程死锁模拟

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

蜡笔小新 2023-12-13 19:12:25
text
后台获取视图对应的字符串

1.帮助类后台获取视图对应的字符串publicclassViewHelper{将View输出为字符串(注：不会执行对应的ac ... [详细]

蜡笔小新 2023-12-13 18:03:01
object
OC学习笔记之@property和@synthesize

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

蜡笔小新 2023-12-14 12:05:06
list
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
Hibernate基础映射

在说Hibernate映射前，我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象，以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]

蜡笔小新 2023-12-14 10:57:47
go
知识图谱——机器大脑中的知识库

本文介绍了知识图谱在机器大脑中的应用，以及搜索引擎在知识图谱方面的发展。以谷歌知识图谱为例，说明了知识图谱的智能化特点。通过搜索引擎用户可以获取更加智能化的答案，如搜索关键词"Marie Curie"，会得到居里夫人的详细信息以及与之相关的历史人物。知识图谱的出现引起了搜索引擎行业的变革，不仅美国的微软必应，中国的百度、搜狗等搜索引擎公司也纷纷推出了自己的知识图谱。 ... [详细]

蜡笔小新 2023-12-14 10:06:19
list
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
object
C#学习教程：在Console中工作但在Windows窗体中不工作的异步代码分享

本文分享了一个关于在C#中使用异步代码的问题，作者在控制台中运行时代码正常工作，但在Windows窗体中却无法正常工作。作者尝试搜索局域网上的主机，但在窗体中计数器没有减少。文章提供了相关的代码和解决思路。 ... [详细]

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

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

蜡笔小新 2023-12-14 09:10:09
object
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56

ahao123

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

Tags | 热门标签

RankList | 热门文章