package Ġstrings Ċ Ċ class ĠA ho Cor as ick Simple Ġ{ ĊĠĠĠ Ġvar Ġprefixes : ĠArray < String > ĊĠĠĠ Ġfun Ġbuild Autom ata ( words : ĠArray < String >): ĠArray < IntArray > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġprefix Map : ĠMap < String , ĠInteger > Ġ= ĠTreeMap () ĊĠĠĠĠĠĠĠ Ġfor Ġ( s Ġin Ġwords ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. s . length ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprefix Map . put ( s . substring ( 0 , Ġi ), Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġprefixes Ġ= Ġprefix Map . keySet (). toArray ( array Of Null s < String >( 0 )) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġprefixes . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprefix Map . put ( prefixes [ i ], Ġi ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġtransitions Ġ= ĠArray ( prefixes . size ) Ġ{ ĠInt Array ( ALPH AB ET _ SIZE ) Ġ} ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġprefixes . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil ĠAL PH AB ET _ SIZE ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġs Ġ= Ġprefixes [ i ] Ġ+ Ġ(' a '. toInt () Ġ+ Ġj ) Ġas ĠChar ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ(! prefix Map . containsKey ( s )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Ġ= Ġs . substring ( 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtransitions [ i ][ j ] Ġ= Ġprefix Map [ s ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġtransitions ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠAL PH AB ET _ SIZE Ġ= Ġ 2 6 ĊĊĠĠĠĠĠĠĠ Ġ// ĠUsage Ġexample ĊĠĠĠĠĠĠĠ Ġfun Ġmain ( args : ĠArray < String ?> ?) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġautom aton Ġ= ĠA ho Cor as ick Simple () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtransitions Ġ= Ġautom aton . build Autom ata ( array Of (" abc ", Ġ" bc ")) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġ" z ab cbc " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġstate Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġs . length ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠSystem . out . println ( s . substring ( 0 , Ġi ). toString () Ġ+ Ġ" Ġ" Ġ+ Ġautom aton . prefixes [ state ]) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġstate Ġ= Ġtransitions [ state ][ s . charAt ( i ) Ġ- Ġ' a '] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ