title: KMP算法date: 2020-11-15 23:52:07
tags: 学习
categories: 学习
mathjax: true

KMP算法

在b站看的天勤率辉考研数据结构

1. 指针不需要回溯

2. 匹配速度快—-

1 基本思路
1.1 模式串和主串中字符一一比较，直到找到不同处
1.2 前n个字符一定是相同的，现在找最大公共前后缀
1.3 将移动模式串使得模式串中的前缀位对应主串中的后缀位

1.4 继续比较

2 注意
2.1 最大公共前后缀要小于本身
2.2 如果某一时刻模式串尾已经超出主串长度，则匹配失败
2.3 公共前后缀可以交叉，前缀中的某部分可以在后缀中，只要能让模式串移动就行

2.4 如果没有公共前后缀，就直接往后移动一位

3 求解方法
3.1 移动一位也就是与下一位比较
3.2 将模式串存于一个数组中，一般习惯从下标为1开始存
3.3 主串与模式串发生不匹配的位置叫做当前位置
3.4 从1号位开始比较
3.4.1 1号位不匹配则与下一位比较
3.4.2 1号位匹配，而2号位不匹配，则公共前后缀相同，违反2.1，即公共前后缀长度为0，1号位与当前位置比较

3.5 发生不匹配，则模式串中前缀的下一位与当前位置比较

4 注意
4.1 所谓指针在主串上，当前位置是主串上的位置
4.2 模式串0号位默认不存储数据，从1号位开始存
4.3 如果公共前后缀长度位n，则模式串上n+1号位与当前位置比较。这样除了1号位就不匹配时没有公共前后缀，其他的都有（最多长度为0），所以可以把1号位不匹配的情况单独出来，其他情况按以上规律
4.4 next数组
求模式串每一位失配时的公共前后缀长度，将其加一存到一个数组中就是next数组。设1号位的公共前后缀长度为-1，这样next数组第一位是0.

*4.5 求出next数组后就知道每一位失配后下一步的操作

以上是一种手工操作
5 改进方法求next数组
5.1 设next[j]=t，则j号位失配时，前面的公共前后缀长度是t-1。
5.2 那么p[1]p[j-1]是后缀
5.3 若p[j]=p[t]，则next[j+1]=t+1=next[j]+1
若p[j]!=p[t]，则循环将t赋值为next[t]，直到t=0或满足p[j]=p[t].t=0时next[j+1]=1
5.4 背下来

void getNext(Str substr, int next[])//求next和主串没关系
{
    int j = 1;
    int t = 0;//next[1]==0
    next[1] = 0;//1号位默认是0
    while(j<substr.length)//j<字符串长度，而不能等于，因为接下来要求j+1的next
    {
        if(t==0||j<substr.ch[j]==substr.ch[t])
        {
            next[j+1]=t+1;
            ++t;
            ++j;
        }
        else
        {
            t=next[t];//j还是不变
        }
    }
}
void KMP(Str str, Str substr, int next[])
{
    int i = 1;int j = 1;//i,j指向主串和模式串的位置
    while(i<=str.length&&j<=substr.length)//i大于时匹配失败，j大于时匹配成功
    {
        if(str.ch[i]==substr.ch[j]||j==0)//若两字符相等，则比较下一位字符是否相等。j==0时模式串中无内容
        {
            ++i;
            ++j;
        }
        else
        {
            j=next[j];//i没有动，就是没有回溯，next[j]就是模式串中应该与主串比较的位置。next[j]为0就是第一位就不匹配，恰好让j也为0，这样可以并入if中
        }
    }
    if(j>substr.length)
    {
        return i-substr.length;//匹配成功，返回主串中位置
    }
    else
    {
        return 0;
    }
}