学步园

【题意】

一篇n个音符的乐谱，求他最长的音乐主题

乐谱由n个小于88的正整数表示

所谓的音乐主题就是两端变化相同的长度大于五的不重合乐谱

比如1 2 3 4 5 6 7 8 9 10

1 2 3 4 5的变化与6 7 8 9 10就相同，且两端不重合

【输入】

多组数据

每组数据第一行为n，表示音符的个数

接下来n个数字表示各个音符

输入以n=0结束

【输出】

对于每组数据输出一个数表示最长的音乐主题，音乐主题不存在输出0

后缀数组的典型应用

09年论文《后缀数组——处理字符串的有力工具》上的例题

大意是先对变化求height，然后二分答案，将问题转化为证明是否存在长度为k的不重合序列

根据后缀数组的性质可知height数组是呈波峰状的，所以按height大于k的条件将其分组，若有一组中最小的sa和最大的sa之差大于k，则存在。

需要注意的是，n=1的情况。

program poj1743;
var
  n,i,j,k,s,e,mid,min,max:longint;
  dl,root,rank,sa,height,total,now,change,keep:array [-1..20001] of longint;
  ok:boolean;

procedure qsort (s,e:longint);
var
  i,j,k,o:longint;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=dl[(s+e) div 2];
  while i<=j do
    begin
      while root[dl[i]]<root[k] do inc(i);
      while root[dl[j]]>root[k] do dec(j);
      if i>j then break;
      o:=dl[i];
      dl[i]:=dl[j];
      dl[j]:=o;
      inc(i);
      dec(j);
    end;
  qsort(s,j);
  qsort(i,e);
end;

begin
  repeat
    read(n);
    if n=0 then break;
    dec(n);
    for i:=0 to n do
      read(root[i]);
    if n=0 then
      begin
        writeln(0);
        continue;
      end;
    for i:=n downto 1 do
      root[i]:=root[i]-root[i-1];
    for i:=1 to n do
      dl[i]:=i;
    qsort(1,n);
    k:=1;
    for i:=1 to n do
      if root[dl[i]]=root[dl[k]] then
        rank[dl[i]]:=k
                             else
        begin
          k:=i;
          rank[dl[i]]:=k;
        end;
    k:=0;
    while 1 shl k<n do
      begin
        for i:=1 to n do
          if i+(1 shl k)>n then change[i]:=0
                           else change[i]:=rank[i+(1 shl k)];
        fillchar(total,sizeof(total),0);
        for i:=1 to n do
          inc(total[change[i]]);
        for i:=1 to n do
          total[i]:=total[i-1]+total[i];
        for i:=1 to n do
          begin
            dl[total[change[i]-1]+1]:=i;
            inc(total[change[i]-1]);
          end;
        fillchar(total,sizeof(total),0);
        ok:=true;
        for i:=1 to n do
          begin
            inc(total[rank[i]]);
            if total[rank[i]]=2 then ok:=false;
          end;
        if ok then break;
        for i:=2 to n do
          total[i]:=total[i]+total[i-1];
        fillchar(now,sizeof(now),0);
        fillchar(keep,sizeof(keep),0);
        for i:=1 to n do
          begin
            if change[dl[i]]<>now[rank[dl[i]]] then
              begin
                now[rank[dl[i]]]:=change[dl[i]];
                total[rank[dl[i]]-1]:=total[rank[dl[i]]-1]+keep[rank[dl[i]]];
                keep[rank[dl[i]]]:=0;
              end;
            inc(keep[rank[dl[i]]]);
            rank[dl[i]]:=total[rank[dl[i]]-1]+1;
          end;
        inc(k);
      end;
    for i:=1 to n do
      sa[rank[i]]:=i;
    fillchar(height,sizeof(height),0);
    for i:=1 to n do
      begin
        if rank[i]=1 then continue;
        k:=height[rank[i-1]]-1;
        if k<0 then k:=0;
        while (sa[rank[i]-1]+k<=n)and(i+k<=n)and(root[i+k]=root[sa[rank[i]-1]+k]) do inc(k);
        height[rank[i]]:=k;
      end;
    s:=1;
    e:=n;
    while s<>e do
      begin
        mid:=s+e-(s+e) div 2;
        min:=maxlongint div 10;
        max:=-maxlongint div 10;
        ok:=false;
        for i:=2 to n do
          if height[i]<mid then
            begin
              min:=maxlongint div 10;
              max:=-maxlongint div 10;
            end
                           else
            begin
              if sa[i]<min then min:=sa[i];
              if sa[i]>max then max:=sa[i];
              if sa[i-1]<min then min:=sa[i-1];
              if sa[i-1]>max then max:=sa[i-1];
              if max-min>mid then
                begin
                  ok:=true;
                  break;
                end;
            end;
        if ok then s:=mid
              else e:=mid - 1;
      end;
    if s+1<5 then writeln(0)
             else writeln(s+1);
  until false;
end.