KMP算法学习记录


KMP算法

作用:用于字符串匹配。

1 准备

前缀:指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀:指不包含第一个字符的所有以最后一个字符结尾的连续子串。
next[](前缀表):最长前后缀数组。
j是从1开始的;
KMP算法学习记录

2 实现

2.1 求next[]

//如果相等长度+1
if(needle[i] == needle[j]){                
      j++;
      next[i] = j;      
  }else{
  //回退
      j = next[j - 1];
  }

完整代码

  vector<int> get_next(string& t){
      vector<int> next(t.size(), -1);
      /*
      j的初始值为-1,值整体右移一位,
      这样j对应的位置就是他应该回退的坐标,否则他的前一位才是应该回退的值
      */
      int i= 0, j = -1; 
      while(i < t.size() - 1){
          if(j == -1 || t[i] == t[j]){                
              j++;
              i++;
              next[i] = j;
              
          }else{
              j = next[j];
          }
      } 
      return next;   
     }

2.2 匹配算法

int strStr(string s, string t) {
    if (t.length() == 0) {
        return 0;
    }
    int n = s.length();
    int m = t.length();
    vector<int> next = get_next(t);
    int i = 0, j = 0;
    while( i < n && j < m){
        if(j == -1 || s[i] == t[j]){                
            j++;
            i++;       
        if (j == m ) return i - m ;
        }else{
            j = next[j];
        }

    } 
    //未找到返回-1
    return -1;
}

3 改进next[]

KMP算法学习记录
我们发现2 3 4 5都是多余的判断,因此next[]得到了改良 nextval[]。

vector<int> get_nextval(string& t){
    vector<int> nextval(needle.size(), -1);      

    int i= 0, j = -1; 

    while(i < t.size() - 1){
        if(j == -1 || t[i] == t[j]){                
            j++;
            i++;
            //如果与s[next[i]]相等则取之前的值
            if(t[i] == t[j]){
                nextval[i] = nextval[j]; 
            }else{
              //如果不等,取现在的值
               nextval[i] = j; 
            }
            
            
        }else{
            j = nextval[j];
        }
    } 

    return nextval;   
}

匹配代码不需要改动,只需要next[]替换为nextval[]即可。

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/282515.html

(0)
上一篇 2022年8月27日
下一篇 2022年8月27日

相关推荐

发表回复

登录后才能评论