Linear Suffix Array Construction by Almost Pure Induced-Sorting Ge Nong∗ Computer Science Department Sun Yat-Sen University Guangzhou 510275, P.R.C. issng@mail.sysu.edu.cn Sen Zhang† Dept. of Math., Comp. Sci. & Stat. SUNY College at Oneonta NY 07104, U.S.A. zhangs@oneonta.edu Wai Hong Chan‡ Department of Mathematics Hong Kong Baptist University Kowloon, Hong Kong dchan@hkbu.edu.hk Abstract We pres