trie树最基本的应用了

不难得到f[i]=f[j] if (s[j+1~i]∈dictionary);

可以用trie树匹配

1 var can,f:array[0..1000010] of boolean; 2     son:array[0..1000010,1..26] of longint; 3     j,l,i,t,n,m,ans:longint; 4     ss:ansistring; 5     s:string; 6  7 procedure add(s:string); 8   var i,l,p,x:longint; 9   begin10     l:=length(s);11     p:=1;12     for i:=l downto 1 do13     begin14       x:=ord(s[i])-96;15       if son[p,x]=-1 then16       begin17         inc(t);18         son[p,x]:=t;19       end;20       p:=son[p,x];21     end;22     can[p]:=true;23   end;24 25 function ask(j:longint):boolean;26   var i,p,x:longint;27   begin28     p:=1;29     while j>0 do30     begin31       x:=ord(ss[j])-96;32       if son[p,x]=-1 then exit(false);33       p:=son[p,x];34       dec(j);35       if f[j] and can[p] then exit(true);36     end;37     exit(false);38   end;39 40 begin41   readln(n,m);42   t:=1;43   fillchar(son,sizeof(son),255);44   for i:=1 to n do45   begin46     readln(s);47     add(s);48   end;49   for i:=1 to m do50   begin51     readln(ss);52     l:=length(ss);53     fillchar(f,sizeof(f),false);54     ans:=0;55     f[0]:=true;56     for j:=1 to l do57     begin58       f[j]:=ask(j);59       if f[j] then ans:=j;60     end;61     writeln(ans);62   end;63 end.