子串：从原串中选取连续的一段，即子串 空串也是子串 后缀：suf(k)为s(k…n)构成的子串 任何子串都是某个后缀的前缀 最长公共前缀 lcp(suf(i),suf(j))
问题：
将所有后缀suf(1),suf(2),suf(N)按照字典序从小到大排序
暴力sort N2 logN 二分+hash : Nlog2N cmp函数中二分suf(i)和suf(j)的lcp return s[i+|lcp|] < s[j+|lcp|] ------- 以上为暴力做法 进入正文： SA[1]排序第1的后缀的开始位置 Rank[i]=后缀suf(i)的排名 Rank[sa[l]] = l sa[Rank[i]] = i 求sa然后得到rank 倍增 sub[i][k]：s从i开始长度为 2k的子串 sub[i][k] = s[i…i+(1<<k)-1 ],超过N的部分都视为
