package Ġstrings Ċ Ċ import Ġjava . util . stream . Int Stream Ċ Ċ // Ġhttps :// en . wikipedia . org / wiki / Suffix _ array Ċ object ĠS uffix Array 2 Ġ{ ĊĠĠĠ Ġ// Ġsuffix Ġarray Ġin ĠO ( n * log ^ 2 ( n )) ĊĠĠĠ Ġfun Ġsuffix Array ( s : ĠCharSequence ): ĠInt Array Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġn : ĠInt Ġ= Ġs . length () ĊĠĠĠĠĠĠĠ Ġval Ġsa : ĠArray < Integer > Ġ= ĠInt Stream . range ( 0 , Ġn ). boxed (). toArray Ġ{ Ġ_ Dummy _. __ Array __() Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġrank : ĠInt Array Ġ= Ġs . chars (). toArray () ĊĠĠĠĠĠĠĠ Ġvar Ġlen Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( len Ġ< Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrank 2 Ġ= ĠLong Array ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġrank 2 [ i ] Ġ= Ġ( rank [ i ]. to Long () Ġshl Ġ 3 2 ) Ġ+ Ġif Ġ( i Ġ+ Ġlen Ġ< Ġn ) Ġrank [ i Ġ+ Ġlen ] Ġ+ Ġ 1 Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ ĠArrays . sort ( sa , ĠComparator . comp aring Long Ġ{ Ġa Ġ-> Ġrank 2 [ a ] Ġ}) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġn ) Ġrank [ sa [ i ]] Ġ= Ġif Ġ( i Ġ> Ġ 0 Ġ&& Ġrank 2 [ sa [ i Ġ- Ġ 1 ]] Ġ== Ġrank 2 [ sa [ i ]]) Ġrank [ sa [ i Ġ- Ġ 1 ]] Ġelse Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġlen Ġ*= Ġ 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠArrays . stream ( sa ). map ToInt ( Integer :: intValue ). toArray () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġrandom Ġtest ĊĠĠĠ Ġfun Ġmain ( args : ĠArray < String ?> ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġrnd Ġ= ĠRandom ( 1 ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( step Ġin Ġ 0 .. 9 9 9 9 9 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn : ĠInt Ġ= Ġrnd . nextInt ( 1 0 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs : ĠStringBuilder Ġ= Ġrnd . ints ( n , Ġ 0 , Ġ 1 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ. collect ({ ĠStringBuilder () Ġ}, Ġ{ Ġsb , Ġi Ġ-> Ġsb . append ((' a ' Ġ+ Ġi )) Ġ}, ĠStringBuilder :: append ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsa Ġ= Ġsuffix Array ( s ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ+ Ġ 1 Ġ< Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( s . substring ( sa [ i ]). compareTo ( s . substring ( sa [ i Ġ+ Ġ 1 ])) Ġ>= Ġ 0 ) Ġthrow ĠRuntimeException () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ ĠSystem . out . println (" Test Ġpassed ") ĊĠĠĠ Ġ} Ċ } Ċ