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.