KMP字元串算法演進(一)

從bp算法開始:

核心思想 循環周遊目标數組 , 如果y[0] == z[0] 則比對y[1] == z[1]

public class StrAl {

    public static void main(String[] args) {
        String targetStr ="微服務的邊界上下文, 使得每一個微服務擁有各自的某一端到端業務場景 (功能)與資料 (資料庫) 。\n" +
                "更重要的是: 當微服務X需調用微服務Y, 則微服務X 與微服務Y的邊界上下文, 将可避免或降低發生, 當微服務Y 運作失敗時, 會影響到微服務 X。";

        String str = "微服務";

        char[] targetchars = targetStr.toCharArray();
        char[] chars = str.toCharArray();
        int count = 0;
        //循環周遊目标數組
        for (int i = 0; i <targetchars.length ; i++) {
            if (targetchars[i]==chars[0]){
                //當周遊到targetchars[i]==chars[0] 時, 去循環周遊比對數組
                System.out.println("比對字元:"+i +"" + targetchars[i]);
                for (int j = 1; j <chars.length ; j++) {
                    //目标數組和比對數組比對
                        if (targetchars[i+j]==chars[j]){
                           if (j==chars.length-1){
                               count++;
                           }
                        }else {
                            continue;
                        }
                }
            }else {
                continue;
            }
        }
        System.out.println("共找到"+count);

    }
}

比對字元:0微
比對字元:16微
比對字元:58微
比對字元:65微
比對字元:72微
比對字元:78微
比對字元:102微
比對字元:118微
共找到8

           

思考:

此方法為暴力方法,當目标數組為n,比對數組為m時,找出問題的複雜度為O(n*m)

疑問點: 當

y[0] != z[0]

y[1] != z[1]

y[2] != z[2] 時, 若z[0] != z[1] != z[2] 是以y[0]~y[2]也對比多做了跟多比對的工作.

是以應該從比對數組來看待問題

考慮以下四種模式

1:思路一

targetStr="微服務的邊界上下文......"
      str ="微服務M"           

由

targetStr[0]=str[0]

targetStr[1]=str[1]

targetStr[2]=str[2]

targetStr[3]!=str[3]

且str[0]!=str[1]!=str[2]!=str[3] 可知

是以

str[0]!=targetStr[1]

str[0]!=targetStr[2]

是以下一輪比對應該從targetStr[3]和str[0]開始

2:思路二

targetStr="的微微微為的的微微為的務的邊界上下文......"
     str ="微微為的務"           

targetStr[1]=str[0]

targetStr[2]=str[1]

targetStr[3]!=str[2]

且str[0]=str[1]

targetStr[0]和str[0] 第一次比對×

targetStr[1]和str[0] 第二次比對√

targetStr[2]和str[1] 第三次比對√

targetStr[3]和str[2] 第三次比對×

接下來應該targetStr[3]和str[1] 開始比較

因為targetStr[0]!=str[0] 又str[0]=str[1]

3： 思路三

targetStr="的的為的的微微為的務的邊界上下文......"
     str ="的的為的的務"           

targetStr[0]和str[0]

targetStr[1]和str[1]

targetStr[3]和str[3]

targetStr[4]和str[4]

且str[0]=str[1]=str[3]=str[4]

是以循環開始後發現

targetStr[5] ！= str[5] 時

接下來應該比對

targetStr[5]和str[2]開始

思路四：

targetStr="的的的的的的的的的的啊......"
             str ="的的的的的務"
           

當targetStr[11] ！= str[5]時

targetStr[11] 和 str[4]

而非targetStr[6] 和 str[0]