NKSEV - Tách từ

Tác giả: RR

Ngôn ngữ: Pascal

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=300111;
  oo=1337377;
type
  trie=^node;
  node=record
         c:integer;
         d:array['a'..'z'] of trie;
       end;
var
  s:ansistring;
  n:longint;
  root:trie;
  d:array[0..MAXN] of longint;
procedure add(var t:trie);
var
  ch:char;
begin
  new(t); t^.c:=0;
  for ch:='a' to 'z' do t^.d[ch]:=nil;
end;
procedure inp;
var
  a:string;
  i,j,m,l:longint;
  x:trie;
begin
  assign(input,FINP); reset(input);
  readln(s); n:=length(s);
  readln(m);
  add(root);
  for i:=1 to m do
    begin
      readln(a); l:=length(a);
      x:=root;
      for j:=l downto 1 do
        begin
          if x^.d[a[j]]=nil then add(x^.d[a[j]]);
          x:=x^.d[a[j]];
        end;
      inc(x^.c);
    end;
  close(input);
end;
procedure solve;
var
  i,j:longint;
  x:trie;
begin
  d[0]:=1;
  for i:=1 to n do
    begin
      x:=root; j:=i;
      while (j>0) and (x^.d[s[j]]<>nil) do
        begin
          x:=x^.d[s[j]];
          dec(j);
          if x^.c=1 then inc(d[i],d[j]);
        end;
      d[i]:=d[i] mod oo;
    end;
  writeln(d[n]);
end;
begin
  inp;
  solve;
end.

Download