Binary search to find the starting index of the kth sub - string
$ l = 1 ; $ h = $ n ; $ start = 0 ; while ( $ l <= $ h ) { $ m = floor ( ( $ l + $ h ) / 2 ) ; if ( $ substring [ $ m ] > $ k ) { $ start = $ m ; $ h = $ m - 1 ; } else if ( $ substring [ $ m ] < $ k ) $ l = $ m + 1 ; else { $ start = $ m ; break ; } }