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.