首页 > 编程语言 >KMP算法

KMP算法

时间:2022-09-22 20:24:02浏览次数:77  
标签:主串 匹配 后缀 模式 next 算法 len KMP

朴素的模式匹配算法

朴素算法就是以主串的每一个字符作为子串的开头,与要匹配的字符串(称为模式串)进行匹配,
匹配失败则主串退回到这次匹配首位的下一位,重新进行匹配。

主串:abcabababcd
          | 
模式串:  ababc

此时匹配失败,那么将跳转到下个首位重新匹配

主串:abcabababcd
       |    
模式串:   ababc

对于主串:00000000000000000000000001与模式串:00000001,查找效率极低,
时间复杂度为O(mn)

KMP算法

kmp算法对于朴素算法的优化在于,每次匹配失败主串的位置不移动,仅仅移动模式串的位置。

主串:abcabababcd
          | 
模式串:  ababc

匹配失败后,仅移动模式串的位置

主串:abcabababcd
          | 
模式串:    ababc

这部分对应的代码为

while (i < len_s && j < len_t) //不要超过最大长度
	{
		if (j == 0 || S[i] == T[j])
		{
			++i;
			++j;
		}//匹配成功继续前进
		else
		{
			j = next[j];//匹配失败模式串跳转到合适位置
		}
	}

这样就节省大量不必要的匹配。
因为这个时候已知模式串前两个字符a,b必定能够匹配

所以问题的关键就在于求解next数组,就是匹配失败后模式串该跳转的位置。
观察模式串:ababc,之所以c匹配失败后能直接跳转到第三个字符(a),是因为abab(没错,不关c的事)这个字符串有相同的真前缀和真后缀(ab)

再举个例子
主串:  zzabcdeeabcdp
                 |     
模式串:   abcdeeabcdq

我们容易看出模式串的最长相同的真前缀和真后缀是abcd,此时p,q匹配失败,
那么我们可以将模式串前面的a,b,c,d与主串后面的a,b,c,d匹配来加速匹配过程,也容易证明跳过的部分一定不能匹配(如果有,那么最长相同真前缀与真后缀将增加),那么接下来匹配的位置就是:

主串:  zzabcdeeabcdp
                 |     
模式串:         abcdeeabcdq

那么现在问题就变成了寻找一个字符串的最长相同的真前缀和真后缀。
这个过程就是模式串自己与自己匹配的过程。

现有模式串abcab,我们来模拟下自己与自己匹配的过程,用len[i],表示前i个字符中最长相同的真前缀和真后缀的长度。
串1:abcab
    |
串2: abcab
首位就不用匹配了,len[1]=0,此时a,b不匹配,那么len[2]=0。
 
串1:abcab
     |
串2:  abcab
不匹配,len[3]=0。
 
串1:abcab
      |
串2:   abcab
成功匹配,那么len[4]=1。 
 
串1:abcab
       |
串2:    abcab
成功,len[5]=2

由于知道了len[i]的大小就是知道了失败后匹配的位置,所以串2匹配时,串2移动的位置可以由len得到,所以模式串自己与自己匹配的过程也使用了kmp。

例题P3375 【模板】KMP字符串匹配
参考代码

//next数组加了优化,ans就是上面的len
//为了方便,用ans[i]表示ans[i-1]的最长相同的真前缀和真后缀
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s1[N], s2[N];
#define next _next
int next[N];
int n1, n2;
int ans[N];
void get_next()
{
    int i = 1, k = 0;
    next[i] = 0;
    ans[i] = 0;
    while (i <= n2)
    {
        if (k == 0 || s2[i] == s2[k])
        {//满足这个条件就相当于已经找到了部分相同的真前缀和真后缀
            ++i;++k;
            if (s2[i] != s2[k])
            {
                ans[i] = k - 1;
                next[i] = k;
                k = next[k];
                
            }//若两个字符相等,可直接继承移动的位置
            else next[i] = next[k], ans[i] = k-1;
        }//匹配失败移动到对应位置
        else k = next[k];
    }
}
int main()
{
    scanf("%s", s1 + 1);
    n1 = strlen(s1 + 1);
    scanf("%s", s2 + 1);
    n2 = strlen(s2 + 1);
    s2[n2 + 1] = 'a';//相当于是个结束标志
    n2++;
    get_next();
    if (n2 <= n1 + 1){
        int t = 1; 
        for (int i = 1; i<= n1; ){
            if (t == 0 || s1[i] == s2[t])
            {
                ++i;
                ++t;
                if (t == n2){
                    printf ("%d\n", i - n2 +1);
                    t = next[t];
                    
                }
            }
            else t = next[t];
        }
    }
    for (int i = 2;i <= n2; ++i)
    printf ("%d ", ans[i]);
   return 0;
}

标签:主串,匹配,后缀,模式,next,算法,len,KMP
From: https://www.cnblogs.com/hetailang/p/16704712.html

相关文章

  • python基础__十大经典排序算法
    用Python实现十大经典排序算法!排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序......
  • 一段式SM3算法的实现
    C语言#pragmaonce//C语言实现的一段式SM3算法#include<stdio.h>#include<memory>//定义初始值IV,初始值IV是一个常数unsignedcharIV[256/8]{0x73,0x80......
  • Vue源码解析——虚拟DOM和diff算法
    前置环境:1.手写h函数vnode.js//默认暴露exportdefaultfunction(sel,data,children,text,elm){return{sel,data,children,text,elm}}h.jsim......
  • 算法题中常用的C++函数
    一、向vector容器中增添元素1、在末尾增添一个元素push_back()2、在任意地方插入一个或多个元素insert()#include<iostream>#include<vector>//注意这......
  • Hash算法
    Hash算法是什么哈希(hash)也翻译作散列。Hash算法,是将一个不定长的输入,通过散列函数变换成一个定长的输出,即散列值,这个值就是Hash值。Hash算法只是一个定义,并没有规定具体......
  • 计算机系统结构大题精讲2-LRU替换算法
    LRU近期最少使用算法1、考虑一个920字的程序,其访问虚存的地址流为:23、216、156、618、382、490、492、868、916、728。若页面大小为200字,主存容量为600字,采用LRU算法。请......
  • 算法 玩转数据结构 2-2 二次封装属于我们自己的数组
    1重点关注1.1索引使用数组最大的优点:快速查询。scores[2]·数组最好应用于“索引有语意”的情况。·但并非所有有语意的索引都适用于数组(例如,以身份......
  • 对公众号算法题的补充和思考
    (其实就是因为公众号不能修改文章内容,现在也没有留言功能,所以才专门写篇文章来进行补充,我会利用好标题的索引功能,方便大家快速查找到想要看的题目;至于为什么用公众号发算法......
  • 【学习笔记】KMP字符串匹配
    字符串匹配——KMP算法给定两个字符串s1和s2,询问s2在s1中出现的位置(定义为出现时的第一个字符在s1中的位置)暴力枚举看到字符串匹配(如果你还不会KMP/Hash的话),八成是......
  • 算法 玩转数据结构 2-1 使用java中的数组
    1重点关注1.1idea新建Java项目newproject--》java--》选择jdk--》next--》createprojectfromtemplate--》Commandlineapp--》next--》输入工程名......