字符串匹配

朴素算法=BF算法=暴力算法

KMP算法

• 去除朴素算法中 配对不上的 和 已配对过的 比较过程

• 什么是KMP中的next数组

  1. next数组的用途
     next记录着：匹配子串的每个下标位往前数，有几个字符和匹配开头连续一样。这个数值可以在匹配到该下标时，直接跳过前面下标位个数的比较，直接比较子串的第下标位置和被匹配字符串的下一个字符。

  2. 代码实现计算next数组

     publib int[] 获取next数组(String 匹配子串){
     
        int[] next数组=new int[匹配子串.length];
        next数组[0]=-1;//由于匹配从1开始，所以初始化next数组的一个数据
        
        int 匹配子串的下标=1;
        int next数组的对应下标=0;
        
        while(匹配子串的下标<匹配子串.length){
                if(next数组的对应下标==0||匹配子串.charAt(匹配子串的下标)==匹配子串.cartAt(next数组的对应下标)){
                        next数组[++匹配子串的下标]=++next数组的对应下标;
                }else{
                        next数组的对应下标=next[next数组的对应下标];//这是关键部分：通过相同子串的交换关系，不断将匹配范围缩小
                }
        }
     }
     

• 使用next数组进行字符串匹配

  
  public void matcher(char[] str,char subStr){
      int[] next=new int[subStr.length()]; //根据子串生成next数组
      int i=0;//str字符串匹配到第i个字符
      int j=0;//子串匹配到第j个字符
      while(i<str.length()&&j<subStr.length()){
          if(str[i]==subStr[j]){ //
              i++;
              j++;
          }else if(j==-1){
              i++;
              j=0;
          }else{
              j=next[j];
          }
      }
      //跑完上面循环：1 被查字符串str都走完了，2 匹配到最后一个子串字符了
      
      if(j==subStr.length()){ //如果是匹配到最后一个字符了，表示匹配成功了
          return i-j;
      }else{
          return -1;
      }
  }
  

• next数组的缺点，什么是nextval数组

BM算法

RK算法