学步园

【题意】

给定一些字符串，询问最长的“链”，“链”就是一些长度相差为1的字符串，且长度差为1的两个字符串长的那个删掉一个字符就跟短的构成（含有各个字母的个数）一样了

求最长链，任意输出一个即可

【输入】

若干行，每行一个字符处

【输出】

从短到长输出字符串

这道题将所有字符串按长度排序从长到短进行dp

对于每个字符串hash一下，枚举当前串加一个字符的字符串，然后hash判断有没有，有了将通往的值+1看是不是比当前最优长，再记一下最优从哪来的

hash必须记录hash值对应的字符串，数据很威武，直接搞重合率略高

program poj2004;
const
  maxn=5466123;
  k=37;
var
  ans,max,min,n,i,j:longint;
  quick:array ['a'..'z'] of longint;
  root,st:array [0..10001] of string[20];
  long,last,f,dl:array [0..10001] of longint;
  rehash:array [0..maxn] of longint;
  anti:array [0..maxn] of string[20];
  temp:char;

procedure swap (var a,b:longint);inline;
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

function sort (now:string):string;inline;
var
  i,j,l:longint;
  temp:char;
begin
  l:=length(now);
  for i:=1 to l-1 do
    for j:=i+1 to l do
      if now[i]>now[j] then
        begin
          temp:=now[i];
          now[i]:=now[j];
          now[j]:=temp;
        end;
  exit(now);
end;

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

function hash (now:string):longint;inline;
var
  i:longint;
  s:longint;
begin
  s:=0;
  for i:=1 to length(now) do
    begin
      s:=s+quick[now[i]];
      if s>=maxn then s:=s-maxn;
    end;
  now:=sort(now);
  while (rehash[s]<>0)and(anti[s]<>now) do
    begin
      inc(s);
      if s=maxn then s:=s-maxn;
    end;
  exit(s);
end;

begin
  quick['a']:=173;
  for temp:='b' to 'z' do
    quick[temp]:=(quick[pred(temp)]*(k+ord(temp))) mod maxn;
  max:=-maxlongint;
  min:=maxlongint;
  n:=0;
  while not seekeof do
    begin
      inc(n);
      readln(root[n]);
      long[n]:=length(root[n]);
      if long[n]>max then max:=long[n];
      if long[n]<min then min:=long[n];
      dl[n]:=n;
    end;
  qsort(1,n);
  for i:=1 to n do
    begin
      j:=hash(root[dl[i]]);
      rehash[j]:=i;
      anti[j]:=sort(root[dl[i]]);
    end;
  ans:=n;
  for i:=n downto 1 do
    begin
      f[i]:=1;
      last[i]:=0;
      if long[dl[i]]=long[dl[n]] then continue;
      for temp:='a' to 'z' do
        begin
          j:=hash(root[dl[i]]+temp);
          if (rehash[j]<>0)and(rehash[j]>i)and(f[rehash[j]]+1>f[i]) then
            begin
              f[i]:=f[rehash[j]]+1;
              last[i]:=rehash[j];
            end;
        end;
      if f[i]>f[ans] then ans:=i;
      if f[i]=max-min+1 then break;
    end;
  i:=ans;
  repeat
    writeln(root[dl[i]]);
    i:=last[i];
  until i=0;
end.