题目描述

后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者 DC3 算法实现，这超出了我们的讨论范围。

在本题中，我们希望使用快排、Hash 与二分实现一个简单的 O(nlog2n) 的后缀数组求法。

详细地说，给定一个长度为 n 的字符串 S（下标 0∼n−1），我们可以用整数 k(0≤k<n) 表示字符串 S 的后缀 S(k∼n−1)。

把字符串 S 的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。

额外地，我们考虑排名为 i 的后缀与排名为 i−1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。

我们的任务就是求出 SA 与 Height 这两个数组。

输入格式
输入一个字符串，其长度不超过 30 万。

字符串由小写字母构成。

输出格式
第一行为数组 SA，相邻两个整数用 1 个空格隔开。

第二行为数组 Height，相邻两个整数用 1 个空格隔开，我们规定 Height[1]=0。

样例

输入样例：
ponoiiipoi
输出样例：
9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

算法1

yxc 在线教学

时间复杂度

$O(n * (logn) * (logn))$

参考文献

JAVA 代码

/**
 * 
 * 后缀数组: 
 *  对所有的后缀字符串 开始的下标 进行排序
 * 
 * 1. 对所有的后缀进行排序
 * 2. 对排序之后的相邻的两个字符串，求其公共前缀的最大长度
 * 
 * output : 运行时间 : 32940 ms
 **/

//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Comparator;
import java.util.Collections;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
    static class HashStringTemplate {
        static int base = 131;
        final boolean reverse; //是否倒序计算
        final String line;
        int[] h;
        int[] p;

        public HashStringTemplate(String line, boolean reverse) {
            this.line = line;
            this.reverse = reverse;
            onConstructor();
        }

        /**
         * 构造 hash tables
         */
        void onConstructor() {
            h = new int[line.length() + 1];
            p = new int[line.length() + 1];
            p[0] = 1;
            int n = line.length();
            if (!reverse) {
                for (int i = 1; i <= n; i++) {
                    h[i] = h[i - 1] * base + line.charAt(i - 1) - 'a' + 1;
                    p[i] = p[i - 1] * base;
                }
            } else {
                for (int i = 1, j = n - 1; i <= n; i++, j--) {
                    h[i] = h[i - 1] * base + line.charAt(j) - 'a' + 1;
                    p[i] = p[i - 1] * base;
                }
            }
        }

        /**
         * 传进来的下标 从 1开始
         *
         * @param l
         * @param r
         * @return
         */
        public long getInternalHashVal(int l, int r) {
            int n = line.length();
            if (!reverse) return h[r] - h[l - 1] * p[r - l + 1];
            else return h[n - l + 1] - h[n - r + 1] * p[r - l + 1];
        }

        /**
         * TODO 拿到两个字符的公共前缀的长度 (为了统一 传进来的下标从1开始)
         *
         * @param a
         * @param b
         * @return
         */
        public int getMaxCommonPrefixLen(int a, int b) {
            int n = line.length();
            int l = 0, r = Math.min(n - a + 1, n - b + 1);
            //二分 找最后一个出现的相同字符
            while (l < r) {
                int m = l + r + 1 >> 1;
                if (getInternalHashVal(a, a + m - 1) != getInternalHashVal(b, b + m - 1)) r = m - 1;
                else l = m;
            }
            return l;
        }

        public int getLen() {
            return line.length();
        }

        /**
         * 传进来的下标 从1开始
         *
         * @param index
         * @return
         */
        public char getChar(int index) {
            index--;
            if (index < 0 || index >= getLen()) throw new StringIndexOutOfBoundsException("下标越界：" + index);
            return line.charAt(index);
        }
    }
    /**
     *  对sa数组做了一个类 
     */
    static class StringSaArray {
        final HashStringTemplate template;

        Integer[] sa;

        public StringSaArray(HashStringTemplate template) {
            this.template = template;
            onConstructor();
        }

        void onConstructor() {
            int n = template.getLen();
            sa = new Integer[n];
            for (int i = 0; i < n; i++) sa[i] = i;
        }

        public HashStringTemplate getTemplate() {
            return template;
        }

        public StringSaArray sort() {
            Arrays.sort(sa, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    //字典序 排序
                    o1++;
                    o2++;
                    int n = template.getLen();
                    int commonLen = template.getMaxCommonPrefixLen(o1, o2);
                    int v1 = o1 + commonLen > n ? -1 : (int) template.getChar(o1 + commonLen);
                    int v2 = o2 + commonLen > n ? -1 : (int) template.getChar(o2 + commonLen);
                    return v1 - v2;
                }
            });
            return this;
        }

        public StringSaArray print(String delimiter, boolean printEndLen) {
            int n = template.getLen();
            for (int i = 0; i < n; i++) System.out.print(sa[i] + delimiter);
            if (printEndLen) System.out.println();
            return this;
        }

        /**
         * 排序后 打印相邻的两个sa后缀数组的公共长度
         *
         * @param delimiter
         */
        public StringSaArray printTwoNearSaMaxCommonPrefixLen(String delimiter, boolean printEndLen) {
            int n = template.getLen();
            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    System.out.print(0 + delimiter);
                } else {
                    System.out.print(template.getMaxCommonPrefixLen(sa[i - 1] + 1, sa[i] + 1) + delimiter);
                }
            }
            if (printEndLen) System.out.println();
            return this;
        }
        public static StringSaArray newInstance(HashStringTemplate t){
           return new StringSaArray(t);
        }
        public static StringSaArray newInstance(String s, boolean reverse){
           return newInstance(new HashStringTemplate(s,reverse));
        }

    }
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
          StringSaArray
         .newInstance(sc.next(),false)
         .sort()
         .print(" ", true)
         .printTwoNearSaMaxCommonPrefixLen(" ",false);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla