先定义一个字符串s，假设它的长度为n

先定义一个字符串s，假设它的长度为n，s[i]表示第i个元素 ，s[i…]代表以s[i]开头且包含s[i]的后缀。我们定义新的数组 sa[i]为一个0-n的排列，且sa[i]为后缀s[i…]在所有后缀中按 照从小到大排序的排名。最后定义rank是sa的反函数。

for(int k=1;k<=n;k<<=1){

for(int i=n-k+1;i<=n;i++)y[++num]=i;

for(int i=1;i<=n;i++)x[i]=0;

while((i+k<=n)&&(j+k<=n)&&(s[i+k]==s[j+k]))k++;