第五章文字列特集(下)

1、接尾辞配列
私がここで書いたのは本当にイメージが悪いので、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{//                        ，           
        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平方レベルに達すると何とかして低減され、接尾辞配列を求めるために倍増法と呼ばれる方法がある(接尾辞配列を求める過程を簡略化しただけで彼のソート)

import java.util.Arrays;

public class SuffixArray {
    public static void main(String[] args) {
        match();  //      5
    }
    
    static void match(){
        String s = "ABABABABB";
        String p = "BABB";
//        SuffixArray.Suff[] sa = SuffixArray.getSa(s); //     
        Suff[] sa = getSa2(s); //     
        int l = 0;
        int r = s.length()-1;
        //      ，nlog(m)
        while(r>=l){
            int mid = l + ((r-l)>>1);
            //      
            Suff midSuff = sa[mid];
//            String suffStr = midSuff.str;
            String suffStr = s.substring(midSuff.index);
            int compareRes;
            //          ，O(n);
            if (suffStr.length()>=p.length()) {
                compareRes = suffStr.substring(0, p.length()).compareTo(p);
            }else {
                compareRes = suffStr.compareTo(p);
            }
            //              
            if(compareRes == 0){
                System.out.println(midSuff.index);
                break;
            }else if (compareRes<0) {
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
    }
    
    
    /**
     * nlg²n       
     * 
     * @param src
     * @return
     */
    public static Suff[] getSa2(String src) {
        int n = src.length();
        Suff[] sa = new Suff[n];
        for (int i = 0; i < n; i++) {
            sa[i] = new Suff(src.charAt(i), i, src);//      ,     
        }
        Arrays.sort(sa);

        /** rk          */
        int[] rk = new int[n];// suffix array
        rk[sa[0].index] = 1;
        for (int i = 1; i < n; i++) {
            rk[sa[i].index] = rk[sa[i - 1].index];
            if (sa[i].c != sa[i - 1].c)
                rk[sa[i].index]++;
        }
        //    
        for (int k = 2; rk[sa[n - 1].index] < n; k *= 2) {

            final int kk = k;
            Arrays.sort(sa, (o1, o2) -> {
                //          ,       rank
                int i = o1.index;
                int j = o2.index;
                if (rk[i] == rk[j]) {//          
                    if (i + kk / 2 >= n || j + kk / 2 >= n)
                        return -(i - j);//               ,     ,       
                    return rk[i + kk / 2] - rk[j + kk / 2];

                } else {
                    return rk[i] - rk[j];
                }
            });
            /*---   end---*/
            //   rank
            rk[sa[0].index] = 1;
            for (int i = 1; i < n; i++) {
                int i1 = sa[i].index;
                int i2 = sa[i - 1].index;
                rk[i1] = rk[i2];
                try {
                    if (!src.substring(i1, i1 + kk).equals(src.substring(i2, i2 + kk)))
                        rk[i1]++;
                } catch (Exception e) {
                    rk[i1]++;
                }
            }
        }

        return sa;
    }
    
    public static class Suff implements Comparable {
        public char c;//     
        private String src;
        public int index;//        

        public Suff(char c, int index, String src) {
            this.c = c;
            this.index = index;
            this.src = src;
        }

        @Override
        public int compareTo(Suff o2) {
            return this.c - o2.c;
        }

        @Override
        public String toString() {
            return "Suff{" + "char='" + src.substring(index) + '\'' + ", index=" + index + '}';
        }
    }
}

3、高さ配列:
これは難しいですね.直接コードを貼ってください.

static int[] getHeight(String src,Suff[] sa){
        // Suff[] sa = getSa2(src);
        int strLength = src.length();
        int []rk = new int[strLength];
        //      sa              ，             ，         rk。
        //  rank          0~n-1
        for (int i = 0; i < strLength; i++) {
            rk[sa[i].index] = i;
        }
        int []height = new int[strLength];
        // （           i   k     ，  k>0，
        //              k-1     ，   k         ）
        //         O(n)      
        int k = 0;
        for(int i=0;i 0)
                k--;

            for (; j + k < strLength && i + k < strLength; k++) {
                if (src.charAt(j + k) != src.charAt(i + k))
                    break;
            }
            height[rk_i] = k;
            
        }
        return height;
    }

4、尺取法例題:
説明
1つの文字列がちょうど2つの'h'、1つの'i'と1つの'o'を含む場合、私たちはこの文字列をhiho文字列と呼ぶ. 
たとえば「oihateher」、「hugeinputhugeoutput」はhiho文字列です.
小文字のみを含む文字列Sが与えられ、HiはSのすべてのサブストリングの中で、最も短いhiho文字列がどれなのか知りたい.
構想:前の尺取法を参考にする:
ちょうどその数なら、多くても少なくてもいけない.

import java.util.Arrays;
import java.util.Scanner;

class Kruskal{
    static char[] pat =  {'h','i','o'};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s =  sc.next();
        int n = hiho(s);
        System.out.println(n);
    }
    static int hiho(String s){
        int len = s.length();
        int lo = Integer.MAX_VALUE;
        char []s_ch = s.toCharArray();
        int start = -1;
        int end = -1;
        int j=0;
        for(int i=0;i=2&&c2>=1&&c3>=1;
    }
}

5、next配列問題:(next配列の正確な求め方)
http://acm.hdu.edu.cn/showproblem.php?pid=1358

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class test2{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List list = new ArrayList<>();
        while (true){
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            String s = sc.next();
            list.add(s); //   ｓ       
        }
        for(int j=0;j1){
                    System.out.println(i+" "+i/t);
                }
            }
            System.out.println();
        }
    }
    static int[] next(String s){
        if(s ==null || s.length()==0) return null;
        int[] next = new int[s.length()+1];//        ，            ，          
        next[0] = -1;
        if(s.length() ==1){
            return next;
        }
        next[1] =0;
        int j=1;
        int k=  next[j];
        while (j

6、接尾辞配列の応用問題:
1、最も長い繰り返しのサブストリングを求めます:(重ねることができて、交差することができます)
2、最も長い繰り返しのサブストリングを求めます(繰り返してはいけなくて、交差してはいけません)
 
練習問題:
1、fjxmlhxは毎日沼躍魚にブラシをかけられているので、彼は急いであなたがすべての文の中の沼躍魚をブロックするプログラムを書くことを望んでいます(「marshtomp」、大文字と小文字を区別しません).文に成分が欠けないように「fjxmlhx」に統一します.
入力
入力には複数行が含まれます.
各行は200を超えない文字列です.
1行の末尾は次の行の先頭とは関係ありません.
しゅつりょく
出力には複数の行が含まれ、説明に従って変換された結果を入力します.
サンプル入力

The Marshtomp has seen it all before.
marshTomp is beaten by fjxmlhx!
AmarshtompB

サンプル出力

The fjxmlhx has seen it all before.
fjxmlhx is beaten by fjxmlhx!
AfjxmlhxB

 
構想:2つの文字列を格納し、1つは元のstr 1であり、1つは元の文字列の大文字を小文字にする文字列str 2であり、一致するたびにstr 2でマッチングし、位置を得て、置換するときはstr 1とstr 2の同じ位置を置換し、最後にstr 1を出力すればよい.

import java.util.Scanner;

class Main{
    static char[] str_ch= new char[200];
    static char[] lower_ch = new char[200];
    String s1  = "marshtomp";
    String s2 = "fjxmlhx";
    static StringBuffer sb1;
    static StringBuffer sb2;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true){
            String str = sc.nextLine();
            StringBuffer sb1 = new StringBuffer(str);
            String lower = str.toLowerCase();
            StringBuffer sb2 = new StringBuffer(lower);
            int position = lower.indexOf("marshtomp"); //java        ，       
            while (position!=-1){
                sb1.replace(position,position+9,"fjxmlhx");//          ，        ，，StringBuffer                ，       
                sb2.replace(position,position+9,"fjxmlhx");
                position = sb2.indexOf("marshtomp");
            }
            System.out.println(sb1.toString());
        }
    }
}

しかし、私は複雑すぎます.
(?i)つまり、マッチング時に大文字と小文字を区別しない.一致するときに大文字と小文字を区別しないことを示します.

import java.util.Scanner;

public class test2 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            String str = scan.nextLine();
            str = str.replaceAll("(?i)marshtomp","fjxmlhx" );//      ，     ｒｅｐｌａｃｅ      
            System.out.print(str);
            System.out.println();
        }
    }
}