POJ 2217：Secretary（后缀数组）

题目大意：求两个字符串的公共子串。

分析：

  模板题，将两个字符串接起来用不会出现的字符分割，然后求分属两个字符串的相邻后缀lcp的最大值即可。

代码：

program work; typearr=array[0..20001]of longint; varsa,rank,b,tmp,lcp:arr;n,i,m,l,u,ans,t:longint;s,s1,s2:ansistring;ch:char; function compare(i,j,k:longint):longint; var ri,rj:longint; beginif rank[i]<>rank[j] then exit(ord(rank[i]<rank[j]))elsebeginif i+k<=n then ri:=rank[i+k] else ri:=-1;if j+k<=n then rj:=rank[j+k] else rj:=-1;exit(ord(ri<rj));end; end; procedure qsort(l,h,k:longint; var a:arr); var i,j,t,m:longint; begin i:=l; j:=h;m:=a[(i+j) div 2];repeat while compare(a[i],m,k)=1 do inc(i); while compare(m,a[j],k)=1 do dec(j); if i<=j thenbegin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i); dec(j); end; until i>j;if i<h then qsort(i,h,k,a); if j>l then qsort(l,j,k,a); end; procedure work_sa(s:ansistring; var sa:arr); var k,i:longint; beginfor i:=1 to n do begin sa[i]:=i; rank[i]:=ord(s[i]); end;k:=1;while k<=n dobeginqsort(1,n,k,sa);tmp[sa[1]]:=1;for i:=2 to n dotmp[sa[i]]:=tmp[sa[i-1]]+compare(sa[i-1],sa[i],k);rank:=tmp;k:=k*2;end; end; function max(x,y:longint):longint; beginif x>y then max:=x else max:=y; end; procedure work_lcp(s:ansistring;var sa,lcp:arr); var i,j,h:longint; beginfor i:=1 to n do rank[sa[i]]:=i;h:=0; lcp[1]:=0; sa[0]:=0;rank[0]:=0;for i:=1 to n dobeginj:=sa[rank[i]-1];if h>0 then dec(h);while (i+h<=n)and(j+h<=n) dobeginif s[i+h]<>s[j+h] then break; inc(h);end;lcp[rank[i]-1]:=h;end; end; beginreadln(u);for l:=1 to u dobeginreadln(s1); readln(s2);s:=s1+'@'+s2;t:=length(s1);n:=length(s); work_sa(s,sa);work_lcp(s,sa,lcp); ans:=0;for i:=1 to n-1 do beginif ((sa[i]<=t)and(sa[i+1]>=t+2))or((sa[i+1]<=t)and(sa[i]>=t+2)) then ans:=max(ans,lcp[i]);end;writeln('Nejdelsi spolecny retezec ma delku ',ans,'.');end; end. View Code

 

转载于:https://www.cnblogs.com/qtyytq/p/5508405.html

总结

以上是生活随笔为你收集整理的POJ 2217：Secretary（后缀数组）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。