# KMP

**Repository Path**: w1402943677/KMP

## Basic Information

- **Project Name**: KMP
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2018-06-05
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# KMP

#### 项目介绍
{**以下是码云平台说明，您可以替换为您的项目简介**
码云是开源中国推出的基于 Git 的代码托管平台（同时支持 SVN）。专为开发者提供稳定、高效、安全的云端软件开发协作平台
无论是个人、团队、或是企业，都能够用码云实现代码托管、项目管理、协作开发。企业项目请看 [https://gitee.com/enterprises](https://gitee.com/enterprises)}

#### 公式
    模式串移动位数 = 已匹配的字符数 - 对应的部分匹配值
    当next数组元素值为-1时，主串和模式串都往后移一位
    
#### 部分匹配值
    "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例
     
        －　"A"的前缀和后缀都为空集，共有元素的长度为0；
    　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
    　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； 
    　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； 
    　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
    　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；    
    　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

#### next数组的作用

![](https://img-blog.csdn.net/20160924175218047)

#### next数组 ---普通版本
  - 算法首先next[0]=-1,next[1]=0；
  - 之后每一位j的next求解: 
       
       1. 比较j-1字符与next[j-1]是否相等， 
            * 如果相等则next[j]=next[j-1]+1, 
            * 如果不相等，则比较j-1字符与next[next[j-1]]是否相等， 
                - 如果相等则next[next[j-1]]+1, 
                - 如果不相等则继续以此下去，直到next[…]=-1,则next[j]=0.
                
#### next数组 ---升级版本
  普通版本的问题：
  
  当主串str1为sssskkk时；模式串str2为ssssswfp时next为{-1  0  1  2  3  4  0  0  }  ；
  
  当匹配到str1[4]和str2[4]会出现失配，根据next数组，str1[4]接下来分别和str[3]、str[2]、str[1]、str[2]比较，直到比较到next[0]为-1，进行str1[5]和str2[0]比较，这是不明智的，完全可以直接进行str1[5]和str2[0]比较。
  
  针对这种情况，当再str2[j]位置出现失配时，本来按照next数组的指示应采用str2[next[j]] = str1[j]进行下一轮比较，但是我们已经得知str2[j] != str2[j-1]所以一定会再次出现失配情况，所以我们下一轮直接使用str2[next[j]]进行比较。