DS串应用 KMP算法

77 阅读 0 评论 51 点赞

我是靠谱客的博主眼睛大冰棍，最近开发中收集的这篇文章主要介绍DS串应用 KMP算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

刚刚搞懂了KMP，输出一下

把长的叫主串，短的叫模式串

KMP,查找字符串的算法，适用于模式串中有重复子串的情况，便于缩短时间

传统暴力解法是模式串一次一次右移，直到对上

主串 Mstr ，模式串 mstr

KMP 主要是 next数组

用一个next数组存储当模式串中每一个位置失效时对应的next【j】

kmp其实就是找出已配对成功的部分中的首尾重复内容来移动

所以如果尾部的部分不能和前面的部分重叠，

即 mstr【j】！=mstr【next【j】】，就缩短距离，从前面mstr【0】到mstr【next【j】】的部分再找

找到从str【0】开始的能和尾部部分重叠的部分，然后获取下标，代替尾部

要是都没有，那就从str【0】开始比较

KMP应用

当模式串中某位置 mstr【j】与主串 Mstr【j】不相等时时，对应主串中的位置 Mstr【i】应重新和模式串的 mstr【next【j】】去比较，这样就可以滑动节省时间，特别是模式串长的时候；

eg：主 ababaccac 模式串abc

abc

这里匹配不成功，本来是移动一位，继续比较，但是KMP可以移动俩

在next数组中 next[2]=0，也就是和模式串mstr【0】去匹配

(这里是把next【0】放第一个‘a’对应的值，所以‘c' 是next【2】

这样就变成了

主 ababaccac 模式串abc

abc 虽然还是没匹配成功，但一次移动距离增大了

eg 主 aaaabababac 模式串 abac

abac

i==6, j==3 时不成功，next【3】=1； Mastr【6】==’b' 重新和

mstr【next【3】】=b 比较，如下

aaaabababac

abac

再执行一次， i==8, j==3 时不成功，next【3】=1； Mastr【8】==’b' 重新和

mstr【next【3】】=b 比较

aaaabababac

abac

恭喜，匹配成功

next值的用途

图片用的我们老师的ppt，这里我借用来记录我的笔记

如何计算next【】

对于主串来说 next【j】表示，如果mstr【j】和Mstr【i】匹配不成功，mstr【0】应该移动到

i+1-next【j】；（这个没什么卵用，这个我自己发现的）

对于自身来说，表示，如果mstr【j】匹配成功，那么从0到j-1，首尾存在长度为next【j】个相同的子串（如果下标从1开始，则为next【j】-1）

首先，next【0】=-1；-1是指连第0位匹配失效时，无条件右移

next【1】=0；第1位匹配不成时，应该重新和模式串头部mstr【0】开始比较

从第二位开始

next【j】受前一位影响，且跟mstr【j】本身的值没有关系

分俩种情况

下面的图片下标从1开始

代码实现

#include <bits/stdc++.h>
using namespace std;
void KMPGETNEXT(){
    string p; cin>>p;
    int l=p.length();
    int next[l];
    next[0]=-1;
    next[1]=0;
    int i=0;
    int j=next[i];//这里用j 表示next【i】的值
    while (i<l)
    {
        if(p[i]==p[j]||j==next[0]){
            next[++i]=++j;
        }
        else
            j=next[j];//如果第一次找不到，那j缩小，找到与p【i】匹配的段
    }
    for (int k = 0; k <l ; ++k) {
        cout<<next[k];
    }
}
int main()
{

    KMPGETNEXT();
}