LeetCode 28.Implement streStr()文字列マッチング

記事の目次

.文字列マッチング

.Implement str()

暴力クラック

Rabin-Karpアルゴリズム

KMPアルゴリズム

BMアルゴリズム

Sundayアルゴリズム

28.文字列マッチング
28.Implement str()
Implement str()
Return the index of the first occurrence of needle in haystack,or-1 if needle is not part of haystack.
Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:
What shound we return when needle is an empy string?This is a great question to ask during an interview.
For the purpose of this proble、we will return 0 when needle is an empy string.This is consistent to C's str()and Java's indexOf()
暴力クラック
この問題は本質的に文字列のマッチング問題です.暴力的に解決する方法で行うことができます.まず特殊な状況を確立する.

テンプレート列needleとテキスト列haystackが全部空の場合、0

に戻ります.

は、モジュラスが空の場合、0

に戻る.

テンプレート・ストリングがテキスト・ストリングより長い場合、-1

に戻る.
以上はまず確定する三つの特殊な状況です.
続いて暴力的な解読を行います.各文字列は、n-m個の長さとモジュレータの長さと同じサブストリングを生成することができます.ここでnはテキストストリングの長さであり、mはテンプレートストリングの長さであります.その後、テンプレートの列と文字列の文字列を一つずつ合わせます.マッチングが成功すると、マッチングに成功したサブストリングの先頭文字がテキストストリングの位置に直接戻ります.この方式に必要な時間複雑度はO(n−m＋1)mである.

class Solution {
    public int strStr(String haystack, String needle) {
        if((isNullOrEmpty(haystack) && isNullOrEmpty(needle)) || isNullOrEmpty(needle)) {
            return 0;
        }
        if(haystack.length() < needle.length()){
            return -1;
        }
        
        int n = haystack.length();
        int m = needle.length();
        for(int i = 0; i < n-m +1 ;i++){
            if(compareTwoString(haystack.substring(i,i+m),needle)){
                return i;
            }
        }
        return -1;
    }
    public boolean isNullOrEmpty(String s){
        return s == null || s.length() == 0;
    }
    
    public boolean compareTwoString(String s1, String s2){
        int n = s2.length() ;
        for(int i = 0; i < n; i++){
            if(s1.charAt(i) != s2.charAt(i)){
                return false;
            }
        }
        return true;
    }
    
}

Rabin-Karpアルゴリズム
Rabin-Karpアルゴリズムは暴力アルゴリズムの改善である.RKアルゴリズムの考えは、テンプレート・ストリングを数値として見て、同じ規則を用いて同じ長さのテキスト・ストリングのサブストリングの数値を計算することである.数値が違っていたら、この2つの文字列は同じ文字列ではないということです.等しい場合、この2つの文字列は等しい可能性があるということです.同じ文字列があり得る文字列の文字を一つずつマッチさせます.
この方法はテンプレートストリングを事前に処理し,文字列整合の回数を減らすことができる.しかし最悪の場合は暴力の解決と同じです.テンプレートの処理にはO(m)の時間が必要ですが、文字列値の計算にはO(m−n)の時間が必要です.
どのように数値で文字列を表しますか?ここでは秦九韶アルゴリズムを採用しています.ここでは13行目に入ってきたdは進数を表しています.256は256進数を表しています.このような処理方法では、数値が大きすぎると、作業が不便になります.したがって、mod qによって数値が小さくなる.このような処理はhashの処理と似ています.もちろん他の方法でこの数値を計算することもできます.

class Solution {
    public int strStr(String haystack, String needle) {
        if((isNullOrEmpty(haystack) && isNullOrEmpty(needle)) || isNullOrEmpty(needle)) {
            return 0;
        }
        if(haystack.length() < needle.length()){
            return -1;
        }

        return RKM(haystack,needle,256,23);
    }
    
    public int RKM(String haystack,String needle,int d,int  q){
        int n = haystack.length();
        int m = needle.length();
        int h = 1;
        int p = 0;
        int t = 0;
        
        for(int i = 0; i < m -1;i++){
            h = (h*d)%q;
        }
        
        for(int i = 0; i < m;i++){
            p = (d*p + Integer.valueOf(needle.charAt(i))) % q;
            t = (d*t + Integer.valueOf(haystack.charAt(i))) % q;
        }
        
        for(int s = 0; s < n -m + 1; s++){
            if(p == t){
                if(compareTwoString(haystack.substring(s,s+m),needle)){
                    return s;
                }
            }
            
            if(s < n-m ){
                t = (d * (t-haystack.charAt(s)*h) + haystack.charAt(s+m))% q;
                if(t < 0){
                    t = t + q;
                }
            }
        }
        return -1;
    }
    
    public boolean isNullOrEmpty(String s){
        return s == null || s.length() == 0;
    }
    
    public boolean compareTwoString(String s1, String s2){
        int n = s2.length() ;
        for(int i = 0; i < n; i++){
            if(s1.charAt(i) != s2.charAt(i)){
                return false;
            }
        }
        return true;
    }
}

KMPアルゴリズム
KMPアルゴリズムは,より大きな程度で無効な整合を減少させた.たとえば、テンプレートストリングが「a b b」で、テキストストリングが「abacab」です.abacにマッチすると、マッチングできないと分かりやすいですが、2番目のaと1番目のbについても同じように無効であることが分かりやすいです.KMPはnext配列を通じて、オフセット量を変えて直接スキップすることで、無効なマッチングとなります.
abbのようなnext配列は[0,0,1,2]です.nextは次のマッチする文字の下付きを表しています.同じように上の例でもCとのマッチングに失敗した時は、前回のマッチングaが成功したことを知っています.したがって、元の状態に戻るのではなく、前回のマッチングaが成功した状態に戻り、next配列を通じて下付き1の状態に戻りました.つまり、bはcにマッチしません.同じように、私たちはnext配列を通じて0の状態に戻りました.この時は一番原始的な状態に戻りました.だから、KMPは直接元の状態に戻りません.前回のマッチングが成功した状態に戻ります.できるだけ返品を減らすようにします.
next配列をどう求めるかは、これも簡単です.テンプレートの列と自分を比較すればいいです.next[i]は、角度を変えて、iで終わる文字列P 1の真の接尾辞P 2の最長プレフィックス長です.最初の文字の必然は0です.abacを例にします.
next［1］を計算します.P 1は「ab」で、本当に接尾語は「b」です.したがって、接尾語の最長接頭辞は0です.
next［2］を計算します.P 1は「aba」で、本当に接尾語は「a」です.したがって、接尾語の最長プレフィックスは1です.
next[3]:P 1は“abb”で、本当に接尾語は“ab”で、だから本当に接尾語の最長の接頭辞は2です.
KMPの本質思想は自動機の思想と似ています.現在の状態から次のステップの状態がどうなっているかを判断します.next配列は別の解釈です.現在の状態が一致しないと、前のベスト状態にジャンプします.上に述べたように、cがbに合わない時、前のマッチの状態に戻ります.
KMPアルゴリズムはnext配列を計算する時、O(m)の時間が必要です.マッチングにはO(n)の時間が必要ですので、全体の時間複雑度はO(m＋n)です.空間複雑度はO(m)です.

class Solution {
    public int strStr(String haystack, String needle) {
        if((isNullOrEmpty(haystack) && isNullOrEmpty(needle)) || isNullOrEmpty(needle)) {
            return 0;
        }
        if(haystack.length() < needle.length()){
            return -1;
        }
        int n = haystack.length();
        int m = needle.length();
        int[] next = getNext(needle);
        int q = 0;
        for(int i = 0; i < n ;i++){
            while(q > 0 && needle.charAt(q) != haystack.charAt(i)){
                q = next[q -1];
            }
            if(needle.charAt(q) == haystack.charAt(i)){
                q++;
            }
            if( q == m){
                return i - m +1;
            }
            // q = next[q];
        }
        return -1;
    }
    
    public int[] getNext(String needle){
        int m = needle.length();
        int[] next = new int[m];
        next[0] = 0;
        int k = 0;
        for(int i = 1; i < m ; i++){
            while(k > 0 && needle.charAt(k) != needle.charAt(i)){
                k = next[k - 1];
            }
            if(needle.charAt(k)== needle.charAt(i)){
                k ++;
            }
            next[i] = k;
        }
        return next;
    }
    
    public boolean isNullOrEmpty(String s){
        return s == null || s.length() == 0;
    }
}

BMアルゴリズム(Boyer-more)
BMアルゴリズムはある程度のKMPアルゴリズムの最適化である.KMPアルゴリズムは失敗するたびに前回の成功状態に戻ります.しかし、テンプレートストリングにマッチする文字が存在しないと、KMPは何回かのジャンプでテンプレートストリングの最初の文字に戻り、マッチングすることができます.BMアルゴリズムの最大の特徴は、より大きなジャンプを獲得することです.必要はありません.KMPのように何度もジャンプします.
Sundayアルゴリズム
SundayアルゴリズムはKMPアルゴリズムと同様に、オフセットを計算することによって、マッチの回数を減らすことができます.違いはどのようにオフセットするかです.文字列の位置を固定し、テンプレートストリングの方式でアルゴリズムを理解することができます.
Sundayアルゴリズムは主にマッチングの最終位の次の文字に注目しています.この文字を使って、どのようにシフトするかを決定します.2つの場合があります.

この文字はすでにテンプレート・ストリングに存在しています.テンプレート・ストリングの一番右側の文字をテキスト・ストリングの文字に揃えます.すなわち、移動するビット数はテンプレート・ストリングの長さであり、その文字の一番右側に出現する位置

です.

文字がテンプレート・ストリング内に存在しない場合、直接スキップし、移動ビット数はテンプレート・ストリング長＋1

である.
では、next配列を使ってテンプレートの列にマッチする文字を計算する場合、移動する桁数が必要です.
上の二つの場合によっては、13～18行のコードを参考にして、存在しないテンプレートの文字は、テンプレートの列の長さ＋1として設定され、存在するのはテンプレートの列の長さ－その文字の一番右に出現する位置となります.
Sundayアルゴリズムでnext配列を計算する時間はO(m＋文字セットの長さ)で、最悪の場合は暴力クラックになります.時間の複雑さはO(m n)で、平均時間の複雑さはO(n)で、空間の複雑さはO(文字セットの長さ)です.

class Solution {
    public int strStr(String haystack, String needle) {
        if((isNullOrEmpty(haystack) && isNullOrEmpty(needle)) || isNullOrEmpty(needle)) {
            return 0;
        }
        if(haystack.length() < needle.length()){
            return -1;
        }
        int n = haystack.length();
        int m = needle.length();
        int[] next = new int[256];
        // calculate next array
        for(int i = 0; i < next.length - 1;i++){
            next[i] = m + 1;
        }
        for(int i = 0; i < m; i++){
            next[needle.charAt(i)] = m - i;
        }
        
        int s = 0;//haystack position
        int j = 0;//needle position
        while( s <= n -m){
            j = 0;
            while( s + j < n && j < m && haystack.charAt(s+j) == needle.charAt(j)){
                j++;
                if(j == m){
                    return s;
                }
            }
            int max = s+m < n ? s+m : n - 1;
            s += next[haystack.charAt(max)];
        }
        return -1;
    }
    
    public boolean isNullOrEmpty(String s){
        return s == null || s.length() == 0;
    }
}