URAL第一A。。。。后缀数组第一题。。。。。
大白书上关于后缀数组的部分好多bug。。。。。。
总算被我一一坑过去了。。。。。
搞会了后缀数组的正确姿势。。。。
Time Limit:2000MS |
|
Memory Limit:65536KB |
|
64bit IO Format:%I64d & %I64u |
[Submit] [Go
Back] [Status]
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 numberN(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
ofNcapital 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
|
Source
Problem Author:Ilya Grebnov, Nikita Rybak, Dmitry Kovalioff Problem Source:Timus Top Coders: Third Challenge
[Submit] [Go
Back] [Status]
|
|
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=4e5+10;
char s[N];
int sa[N],rank[N],rank2[N],height[N],c[N],*x,*y;
void radix_sort(int n,int sz)
{
memset(c,0,sizeof(c));
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<sz;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
}
void get_sa(char* s,int n,int sz=128)
{
x=rank;y=rank2;
for(int i=0;i<n;i++)
x[i]=s[i],y[i]=i;
radix_sort(n,sz);
for(int len=1;len<n;len<<=1)
{
int yid=0;
for(int i=n-len;i<n;i++) y[yid++]=i;
for(int i=0;i<n;i++) if(sa[i]>=len) y[yid++]=sa[i]-len;
radix_sort(n,sz);
swap(x,y);
x[sa[0]]=yid=0;
for(int i=1;i<n;i++)
{
if(y[sa[i-1]]==y[sa[i]]&&sa[i-1]+len<n&&sa[i]+len<n
&&y[sa[i-1]+len]==y[sa[i]+len])
x[sa[i]]=yid;
else x[sa[i]]=++yid;
}
sz=yid+1;
if(sz>=n) break;
}
for(int i=0;i<n;i++)
rank[i]=x[i];
}
void get_height(char* s,int n)
{
int k=0;
for(int i=0;i<n;i++)
{
if(rank[i]==0) continue;
k=max(0,k-1);
int j=sa[rank[i]-1];
while(s[i+k]==s[j+k]) k++;
height[rank[i]]=k;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
scanf("%s",s);
s[n]=127;
scanf("%s",s+n+1);
int nn=strlen(s);
get_sa(s,nn);
get_height(s,nn);
int be=0,len=0;
for(int i=1;i<nn;i++)
{
if((sa[i]<n&&sa[i-1]>n)||(sa[i]>n&&sa[i-1]<n))
{
if(height[i]>len)
{
be=sa[i]; len=height[i];
}
}
}
for(int i=be;i<be+len;i++) putchar(s[i]);
putchar(10);
}
return 0;
}
分享到:
相关推荐
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
URAL3D
Pascal acm_timus_ural_1148.pas
URAL(Timus Online Judge)部分测试数据 不全
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
Pascal acm_timus_ural_1099.pas
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->...ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
chieves t he integration of optical and st ruct ural design sof tware. Mainly based on black box compo2 nent met hod , t he development of optical and st ruct ural design sof tware is completed using ...
乌拉尔
and the National Geographic Society[5] as 4/5 of the landmass of Eurasia – with the western portion of the latter occupied by Europe – located to the east of the Suez Canal, east of the Ural ...