package Ġcom . l ond og ard . fuzz ym atch Ċ Ċ import Ġkotlin . math . min Ċ Ċ class ĠF uzzy Matcher ( private Ġval Ġscore Config : ĠScore Config Ġ= ĠScore Config ()) Ġ{ ĊĠĠĠ Ġdata Ġclass ĠResult ( val Ġindices : ĠList < Int >, Ġval Ġscore : ĠInt , Ġval Ġtext : ĠString ? Ġ= Ġnull ) ĊĠĠĠ Ġprivate Ġdata Ġclass ĠData Holder ( val Ġtext Left : ĠString , Ġval Ġmatches : ĠList < Int >, Ġval Ġrecursive Results : ĠList < Result >) ĊĊĠĠĠ Ġprivate Ġval Ġempty Result Ġ= ĠResult ( emptyList (), Ġ 0 ) ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġif Ġeach Ġcharacter Ġin Ġpattern Ġis Ġfound Ġse quent ially Ġwithin Ġtext . Ġ~ 3 Ġtimes Ġfaster Ġthan Ġcontains ĊĠĠĠĠ Ġ* Ġ@ param Ġpattern ĠString Ġ- Ġthe Ġpattern Ġto Ġbe Ġfound ĊĠĠĠĠ Ġ* Ġ@ param Ġtext ĠString Ġ- Ġthe Ġtext Ġwhere Ġwe Ġwant Ġto Ġfind Ġthe Ġpattern ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġfuzzy Match Simple ( pattern : ĠString , Ġtext : ĠString ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ// text . contains () ĊĠĠĠĠĠĠĠ Ġvar Ġpattern Idx Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġtext Idx Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġpattern Len Ġ= Ġpattern . length ĊĠĠĠĠĠĠĠ Ġval Ġtext Len Ġ= Ġtext . length ĊĊĠĠĠĠĠĠĠ Ġwhile Ġ( pattern Idx Ġ!= Ġpattern Len Ġ&& Ġtext Idx Ġ!= Ġtext Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( pattern [ pattern Idx ]. toLowerCase () Ġ== Ġtext [ text Idx ]. toLowerCase ()) Ġ++ pattern Idx ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ++ text Idx ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġreturn Ġpattern Len Ġ!= Ġ 0 Ġ&& Ġtext Len Ġ!= Ġ 0 Ġ&& Ġpattern Idx Ġ== Ġpattern Len ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġfuzzy Ġmatch , Ġfinds Ġall Ġpossible Ġmatches Ġand Ġretrieves Ġthe Ġoptimal Ġsolution Ġusing ĠS cor ing Config . ĊĠĠĠĠ Ġ* ĠCurrently Ġonly Ġreturns Ġif Ġfull Ġmatch . ĠElse Ġempty Ġresult Ġreturned . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ param Ġtext : Ġthe Ġtext Ġinput ĊĠĠĠĠ Ġ* Ġ@ param Ġpattern : Ġthe Ġpattern Ġwe Ġwant Ġto Ġmatch Ġto Ġthe Ġtext ĊĠĠĠĠ Ġ* Ġ@ param Ġres : Ġrecursion Ġparam Ġ( ignore Ġit ) ĊĠĠĠĠ Ġ* Ġ@ param Ġtext Len : Ġrecursion Ġparam Ġ( ignore Ġit ) ĊĠĠĠĠ Ġ* Ġ@ param Ġfull Text : Ġrecursion Ġparam Ġ( ignore Ġit ) ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġfuzzy Match Func ( ĊĠĠĠĠĠĠĠ Ġtext : ĠString , ĊĠĠĠĠĠĠĠ Ġpattern : ĠString , ĊĠĠĠĠĠĠĠ Ġres : ĠResult Ġ= Ġempty Result , ĊĠĠĠĠĠĠĠ Ġtext Len : ĠInt Ġ= Ġtext . length , ĊĠĠĠĠĠĠĠ Ġfull Text : ĠString Ġ= Ġtext ĊĠĠĠ Ġ): ĠResult Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpattern . length Ġ> Ġtext . length Ġ|| Ġtext . isEmpty () Ġ-> Ġempty Result ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpattern . isEmpty () Ġ-> Ġres ĊĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrecursive Params Ġ= Ġpattern . fold Indexed ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠData Holder ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġres . indices , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġempty List () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ Ġindex , Ġ( text Left , Ġmatches , Ġrecursive Res ), Ġpattern Char Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext Left . isEmpty () Ġ-> Ġreturn Ġempty Result ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpattern Char . equals ( text Left [ 0 ], Ġtrue ) Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrecursive Result Ġ= Ġfuzzy Match Func ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext Left . drop ( 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpattern . substring ( index ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġres . copy ( indices Ġ= Ġmatches ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext Len , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfull Text ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠData Holder ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext Left . drop ( 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmatches Ġ+ Ġ( text Len Ġ- Ġtext Left . length ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrecursive Res Ġ+ Ġrecursive Result ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġupdated Text Ġ= Ġtext Left . drop While Ġ{ Ġ! it . equals ( pattern Char , Ġtrue ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( updated Text . isEmpty ()) Ġreturn Ġempty Result ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrecursive Result Ġ= Ġfuzzy Match Func ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġupdated Text . drop ( 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpattern . substring ( index ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġres . copy ( indices Ġ= Ġmatches ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtext Len , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfull Text ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠData Holder ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġupdated Text . drop ( 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmatches Ġ+ Ġ( text Len Ġ- Ġupdated Text . length ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrecursive Res Ġ+ Ġrecursive Result ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġresults Ġ= Ġrecursive Params . recursive Results Ġ+ ĠResult ( recursive Params . matches , Ġ 1 0 ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( recursive Params . matches . size Ġ!= Ġpattern . length ) Ġempty Result ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġresults . filter Ġ{ Ġit . score Ġ> Ġ 0 Ġ}. map Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠResult ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġit . indices , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġscoring Function ( it . indices , Ġfull Text ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ}. max By Ġ{ Ġit . score Ġ} ?. copy ( text Ġ= Ġfull Text ) !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠF uzzy Ġmatch Ġpattern Ġon Ġa Ġcollection Ġof Ġtexts . ĠReturns Ġthe Ġtop N Ġresults Ġ( sc oring Ġby ĠScore Config ). ĊĠĠĠĠ Ġ* Ġ@ param Ġtexts : ĠThe Ġcollection Ġof Ġtexts . ĊĠĠĠĠ Ġ* Ġ@ param Ġpattern : ĠThe Ġpattern Ġto Ġmatch Ġon Ġthe Ġtexts ĊĠĠĠĠ Ġ* Ġ@ param Ġtop N : ĠNumber Ġof Ġresults Ġto Ġreturn ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġfuzzy Match ( texts : ĠList < String >, Ġpattern : ĠString , Ġtop N : ĠInt Ġ= Ġ 2 0 ): ĠList < Result > Ġ= ĊĠĠĠĠĠĠĠ Ġif Ġ( pattern . length Ġ== Ġ 1 ) Ġtexts . as Sequence () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġit . contains ( pattern ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. take ( top N ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġmatch Ġ-> ĠResult ( listOf ( match . indexOf ( pattern )), Ġscore Config . first Letter Match , Ġmatch ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. toList () ĊĠĠĠĠĠĠĠ Ġelse Ġtexts ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. map Ġ{ Ġfuzzy Match Func ( it , Ġpattern ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. filter Ġ{ Ġit . score Ġ> Ġ 0 Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. sorted By Descending Ġ{ Ġit . score Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ. take ( top N ) ĊĊĠĠĠ Ġprivate Ġfun Ġscoring Function ( indices : ĠList < Int >, Ġtext : ĠString ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠlistOf ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmin ( 3 , Ġindices [ 0 ]) Ġ* Ġscore Config . un matched Leading Letter , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindices . window ed ( 2 ). map Ġ{ Ġindex Window Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġfirst Letter Ġ= Ġif Ġ( index Window . first () Ġ== Ġ 0 ) Ġscore Config . first Letter Match Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġconsecutive Ġ= Ġif Ġ( index Window . first () Ġ== Ġindex Window . last () Ġ- Ġ 1 ) Ġscore Config . con secutive Match Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġneighbour Ġ= Ġtext [ index Window . first ()] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcamel Case Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( ne ighbour . is LowerCase () Ġ&& Ġtext [ index Window . last ()]. is UpperCase ()) Ġscore Config . camel Case Match Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġseparator Ġ= Ġif Ġ( ne ighbour Ġ== Ġ' Ġ' Ġ|| Ġneighbour Ġ== Ġ'_ ') Ġscore Config . separator Match Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġun matched Ġ= Ġ( indices . last OrNull () Ġ?: Ġtext . length ) Ġ* Ġscore Config . un matched Letter ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfirst Letter Ġ+ Ġconsecutive Ġ+ Ġcamel Case Ġ+ Ġseparator Ġ+ Ġun matched ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ}. sum () ĊĠĠĠĠĠĠĠ Ġ). sum () ĊĠĠĠ Ġ} Ċ }