CHAIN2 - Chuỗi từ

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$ifdef rr}
  {$mode objfpc}
  {$r+,q+,h-}
  {$inline off}
{$else}
  {$mode objfpc}
  {$r-,q-,h+}
  {$inline on}
{$endif}

uses math;
const
  FINP          =       '';
  FOUT          =       '';

type
  trie          =       ^node;
  node          =       record
        u,f     :       longint;
        c       :       array['a'..'z'] of trie;
  end;

var
  f1,f2         :       text;
  root          :       trie;
  s             :       string;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure add(var a:trie); inline;
    var
      c:char;
    begin
      new(a);
      a^.u:=0;
      a^.f:=0;
      for c:='a' to 'z' do
          a^.c[c]:=nil;
    end;

procedure inp;
    var
      n,i:longint;
      p:trie;
    begin
      readln(f1,n);
      add(root);
      for n:=1 to n do
        begin
          readln(f1,s); p:=root;
          for i:=1 to length(s) do
            begin
              if p^.c[s[i]]=nil then add(p^.c[s[i]]);
              p:=p^.c[s[i]];
            end;
          p^.u:=1;
        end;
    end;

procedure dfs(a:trie); inline;
    var
      c:char;
    begin
      a^.f:=a^.u;
      for c:='a' to 'z' do
        if a^.c[c]<>nil then
          begin
            dfs(a^.c[c]);
            a^.f:=max(a^.f,a^.c[c]^.f+a^.u);
          end;
    end;

procedure solve;
    begin
      dfs(root);
      writeln(f2,root^.f);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Download