poj2774求大神
pascal吧
全部回复
仅看楼主
level 5
不知道哪里错了
2014年08月02日 12点08分 1
level 5
Program poj2774;
Var i,j,k,m,n,l,p,mi,ans:longint;
s1,s2,str:ansistring;
sum,sa,tsa,rk,trk,h:array[0..210000] of longint;
Begin
readln(s1); readln(s2);
str:=s1+*$*+s2;
mi:=length(s1)+1;
l:=length(str);
for i:=1 to l do
begin
trk[i]:=ord(str[i]); inc(sum[trk[i]]);
end;
for i:=2 to 255 do
begin
inc(sum[i],sum[i-1]);
end;
for i:=l downto 1 do
begin
sa[sum[trk[i]]]:=i; dec(sum[trk[i]]);
end;
rk[sa[1]]:=1; p:=1;
for i:=2 to l do
begin
if trk[sa[i]]<>trk[sa[i-1]] then inc(p);
rk[sa[i]]:=p;
end;
m:=p; j:=1;
while m<l do
begin
move(rk,trk,sizeof(rk));
fillchar(sum,sizeof(sum),0);
p:=0;
for i:=l-j+1 to l do begin inc(p); tsa[p]:=i; end;
for i:=1 to l do
if sa[i]>j then
begin inc(p); tsa[p]:=sa[i]-j; end;
for i:=1 to l do begin rk[i]:=trk[tsa[i]]; inc(sum[rk[i]]); end;
for i:=2 to m do inc(sum[i],sum[i-1]);
for i:=l downto 1 do begin sa[sum[rk[i]]]:=tsa[i]; dec(sum[rk[i]]); end; rk[sa[1]]:=1; p:=1;
for i:=2 to l do begin
if (trk[sa[i]]<>trk[sa[i-1]]) or (trk[sa[i]+j]<>trk[sa[i-1]+j]) then begin
inc(p); rk[sa[i]]:=p; end;
end;
m:=p; j:=j*2;
end;
h[1]:=0; p:=0;
for i:=1 to l do
begin
if rk[i]=1 then continue;
j:=sa[rk[i]-1];
if (i+p<=l) and (j+p<=l) then
while str[i+p]=str[j+p] do
begin
inc(p);
if (i+p)>l then break;
if (j+p)>l then break;
end;
h[rk[i]]:=p;
if p>0 then dec(p);
end;
for i:=2 to l do
begin
if h[i]>ans then
if ((sa[i]<mi) and (sa[i-1]>mi)) or ((sa[i]>mi) and (sa[i-1]<mi)) then ans:=h[i];
end;
writeln(ans);
End.
2014年08月02日 12点08分 2
新手求罩[乖]
2014年08月02日 13点08分
level 12
题目发上来
2014年08月03日 02点08分 3
level 5
题意】
给定两个字符串A 和B,求最长公共子串的长度。
【输入】
两行,两个公共子串
【输出】
一个数字,表示最长公共子串的长度
2014年08月03日 03点08分 4
level 12
2014年08月05日 14点08分 5
Orz求代码
2014年08月06日 01点08分
Orz求后缀数组模板
2014年08月06日 01点08分
回复 abslime :很笨的办法,一个字一个字对比,会超过要求的时限
2014年08月06日 03点08分
回复 A1Duke :一个一个对比当然会TLE拉,这是要误导他人吗
2014年08月06日 04点08分
level 4
这道题很经典哦,最长公共子序列。可以去看看TYVJ的P1050的题解。这里是我写的代码。
2015年02月04日 13点02分 8
[汗]真是挖的一手好坟。。。
2015年02月05日 01点02分
回复
���ƻ�֮��
:原来是动态规划么。。中文注释你是不是做图的时候加上去的
2015年02月05日 01点02分
1