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]