第五章　字符串专题（下）

１、后缀数组

我在这里写的实在不形象，，推荐一篇blog吧，https://www.cnblogs.com/xiaoyh/p/10322424.html

import java.util.Arrays;

class test3{
    public static void main(String[] args) {
        match();
    }
    static void match(){
        String s = "ABABABABB";
        String p = "BABB";
        suff[] sa = getsa(s); //生成后缀数组(就是已经排序好的)
        int l=0;
        int r = s.length()-1;
        //二分查找
        while (r>=l){
            int mid  = l+((l-r)>>1);
            suff midsuff = sa[mid];
            String suffer = midsuff.str;
            int compare;
            //将后缀与模式串比较
            if(suffer.length()>=p.length()){
                compare = suffer.substring(0,p.length()).compareTo(p); //与子串比
            }else {
                compare = suffer.compareTo(p);
            }
            if(compare == 0){
                System.out.println(midsuff.index);
                break;
            }else if(compare<0){
                l = mid+1;
            }else {
                r= mid-1;
            }
        }
    }
    static suff[] getsa(String src){
        int strlength = src.length();
        suff[] suffixarray = new suff[strlength]; //suffixarry是suff数组，这个suff有三个参数
        for(int i=0;i<strlength;i++){
            String suffi = src.substring(i);
            suffixarray[i] = new suff(suffi,i); //把字符串和源字符串的下标同时存入
        }
        Arrays.sort(suffixarray);//根据ｓｕｆｆ的比较规则进行排序
        return suffixarray;
    }
    public static class suff implements Comparable<suff>{//这里自定义他的原因是对字符串排序的话排玩没有索引，所以这里给他们缝在一起
        public String str;//str是字符串
        public int index;//后缀的起始下标

        public suff(String str,int index){
            super();
            this.str = str;
            this.index = index;
        }

        @Override
        public int compareTo(suff o2) {
            return this.compareTo(o2);
        }

        @Override
        public String toString() {
            return "suff{" +
                    "str='" + str + '\'' +
                    ", index=" + index +
                    '}';
        }
    }
}

倍增法

上面求后缀数组的方式时间复杂度为n²log(n)，一般来说，时间复杂度只要达到了n平方级别都要想办法降低，于是就有一种叫做倍增法的方法来求后缀数组（只是简化了求后缀数组的过程　他的排序）