import Ġjava . util .* Ċ Ċ /** Ċ Ġ* ĠAdd Ġall Ġthe Ġwords Ġyou Ġneed Ġwith Ġthe Ġadd Ġfunction Ċ Ġ* Ġthen Ġcall Ġbuild Ġfailures Ġonce Ġyou 're Ġdone Ġsetting Ġup Ġthe Ġdictionary Ċ Ġ* Ċ Ġ* ĠYou 'll Ġlikely Ġneed Ġto Ġmess Ġwith Ġcount Matches Ġto Ġmake Ġit Ġdo Ġexactly Ġwhat Ġyou Ġneed Ġfor Ġyour Ġcurrent Ġproblem Ċ Ġ*/ Ċ private Ġclass ĠA ho Cor as ick ( n : ĠInt ) Ġ{ ĊĠĠĠ Ġval Ġtrie Ġ= ĠArray ( n ) Ġ{ ĠInt Array ( 2 6 ) Ġ{ Ġ- 1 Ġ} Ġ} ĊĠĠĠ Ġval Ġword Id Ġ= ĠInt Array ( n ) Ġ{ Ġ- 1 Ġ} ĊĠĠĠ Ġvar Ġnum Nodes Ġ= Ġ 1 ĊĠĠĠ Ġval Ġword To Node Ġ= Ġmutable ListOf < Int >() ĊĠĠĠ Ġval Ġword Count Ġ= Ġmutable ListOf < Int >() ĊĠĠĠ Ġval Ġcompleted Words Ġ= ĠArray ( n ) Ġ{ ĠTree Set < Int >() Ġ} ĊĠĠĠ Ġval Ġfail Ġ= ĠInt Array ( n ) Ġ{ Ġ- 1 Ġ} ĊĊĠĠĠ Ġfun Ġadd All And Build ( dict : ĠList < String >) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( s Ġin Ġdict ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġadd ( s ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġbuild Failures () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġadd ( s : ĠString ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcur Node Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġcur Depth Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġcur Idx Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( cur Idx Ġ!= Ġs . length ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġc Ġ= Ġs [ cur Idx ] Ġ- Ġ' a ' ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( trie [ cur Node ][ c ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrie [ cur Node ][ c ] Ġ= Ġnum Nodes ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Node Ġ= Ġtrie [ cur Node ][ c ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Depth ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Idx ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( word Id [ cur Node ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġword Id [ cur Node ] Ġ= Ġword To Node . size ĊĠĠĠĠĠĠĠĠĠĠĠ Ġword Count Ġ+= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġword To Node Ġ+= Ġcur Node ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcompleted Words [ cur Node ]. add ( word Id [ cur Node ]) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġbuild Failures () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġqueue Ġ= ĠArray Deque < Int >() ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġ 0 Ġuntil Ġ 2 6 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( trie [ 0 ][ c ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtrie [ 0 ][ c ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfail [ trie [ 0 ][ c ]] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue Ġ+= Ġtrie [ 0 ][ c ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ( queue . isNotEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcur State Ġ= Ġqueue . poll () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġ 0 Ġuntil Ġ 2 6 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( trie [ cur State ][ c ] Ġ!= Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġfailure Ġ= Ġfail [ cur State ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( trie [ failure ][ c ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfailure Ġ= Ġfail [ failure ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfailure Ġ= Ġtrie [ failure ][ c ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfail [ trie [ cur State ][ c ]] Ġ= Ġfailure ĊĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// stuff ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcompleted Words [ trie [ cur State ][ c ]]. addAll ( completed Words [ failure ]) ĊĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġqueue Ġ+= Ġtrie [ cur State ][ c ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġnext State ( cur State : ĠInt , Ġch : ĠChar ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġc Ġ= Ġch Ġ- Ġ' a ' ĊĠĠĠĠĠĠĠ Ġvar Ġret Ġ= Ġcur State ĊĠĠĠĠĠĠĠ Ġwhile Ġ( trie [ ret ][ c ] Ġ== Ġ- 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġret Ġ= Ġfail [ ret ] ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġtrie [ ret ][ c ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcount Matches ( s : ĠString ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcur State Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġct Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( c Ġin Ġs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur State Ġ= Ġnext State ( cur State , Ġc ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġct Ġ+= Ġcompleted Words [ cur State ]. size ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġct ĊĠĠĠ Ġ} Ċ }