您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

经典算法kmp,大神级的存在

时间:2022-06-01 13:22:13  来源:  作者:小智雅汇

对于字符串匹配,如用一个长度为m的模式串去匹配一个长度为n的主串,我们可以使用暴力法(BF,Brute Force),其时间复杂度为O(m*n)。

字符串匹配kmp算法的时间复杂度只需要O(m+n)。

使用变量 i, j 表示主串s[]和模式串t[]的下标, 第一轮匹配:

经典算法kmp,大神级的存在

 

kmp算法认为,i 可以不回退(BF要求退回到主串的第2个位置(第几轮就是第几个位置)),而 j 可以回退到第2个位置,即 j=2(BF要求退回到每1个字符的位置)。

经典算法kmp,大神级的存在

 

即使使用暴力破解,几轮迭代后,也会迭代匹配到此位置,所以上述 i,j 的回退不影响整体结果的正确性。

模式串此时回退为什么是2呢?

看下面已匹配的公共部分:

经典算法kmp,大神级的存在

 

主串以不匹配的位置为基准,考虑前面的字符abaab,有后缀ab与模式串abaabe最前面的字符前缀ab相等。

也就是模式串本身abaab,有最大后缀部分ab与最大前缀ab相等,相等字符的长度为2。

从上图可见,假设一个字符串长度为n,其最大前缀和后缀相等的字符数量不会超过n/2,例如:

abcdabcd,长度为8,8/2=4,其最大前缀和后缀相等的字符串abcd最大可能的长度为4。

如何暴力计算下面字符的最大前缀和后缀字符串的长度L呢?

abcdaabbcdeabcd,长度n为15,其L不会超过n/2=7,暴力匹配的思路可以描述为:

前1个字符与后1个字符是否相等?

前2个字符与后2个字符是否相等?

前3个字符与后3个字符是否相等?

……

前n/2个字符与后n/2个字符是否相等?

暴力匹配的思路也可以描述为:

前n/2=7个字符与后n/2=7个字符是否相等?

abcdaabbcdeabcd

前n/2-1=6个字符与后n/2-1=6个字符是否相等?

abcdaabbcdeabcd

前n/2-2=5个字符与后n/2-2=5个字符是否相等?

abcdaabbcdeabcd

abcdaabbcdeabcd

前n/2-3=4个字符与后n/2-3=4个字符是否相等?

abcdaabbcdeabcd

此时相等,则L为4。

对于模式串abaabe,如何计算各个子串对应的最大前缀与后缀字符串数量(j回退到的位置)?

abaab

2

abaa

1

aba

1

ab

0

a

-1

图示:

经典算法kmp,大神级的存在

 

对应代码:

int *getNextArray(char t[]) // 动态规划
{
    int n = strlen(t);
    int *next = (int*)malloc(sizeof(int)*n);
    next[0] = -1;
    next[1] = 0;
    int k;
    for (int j = 2; j < n; j++) {
        k=next[j-1];            // 先假设
        while (k!=-1) {
            if (t[j - 1] == t[k]) {
                next[j] = k + 1;
                break;
            }else
                k = next[k];    // 回退
            next[j] = 0;  //当k==-1而跳出循环时,next[j] = 0,否则next[j]会在break之前被赋值
        }
    }
    return next;
}

对于模式串T的下标 j 回退位置next[]的求解方法,KMP算法应用的动态规划的思想:

首先大胆假设next[j]=k,则

经典算法kmp,大神级的存在

 

那么next[j+1]=?

也就是以上子串再分别多考虑一个随后的字符:

经典算法kmp,大神级的存在

 

可以区分这两个字符在相等和不等的情况下分别考虑:

经典算法kmp,大神级的存在

 

有了确定模式串回退位置的数组,字符串匹配剩下的代码就相对较容易了。

demo c code:

#include <stdio.h>
#include <malloc.h>
#include <string.h>
// 对主串s和模式串t进行KMP模式匹配
// 计算模式串t需要回退的位置(BF是回退到0)
int *getNextArray(char t[]) // 动态规划
{
    int n = strlen(t);
    int *next = (int*)malloc(sizeof(int)*n);
    next[0] = -1;
    next[1] = 0;
    int k;
    for (int j = 2; j < n; j++) {
        k=next[j-1];            // 先假设
        while (k!=-1) {
            if (t[j - 1] == t[k]) {
                next[j] = k + 1;
                break;
            }else
                k = next[k];    // 回退
            next[j] = 0;  //当k==-1而跳出循环时,next[j] = 0,否则next[j]会在break之前被赋值
        }
    }
    return next;
}

/**
 * 对主串s和模式串t进行KMP模式匹配
 * @param s 主串
 * @param t 模式串
 * @return 若匹配成功,返回t在s中的位置(第一个相同字符对应的位置),若匹配失败,返回-1
 */
int kmpMatch(char* s, char* t){
    int *next = getNextArray(t);
    int i = 0, j = 0;
    while (i<(int)strlen(s) && j<(int)strlen(t)){
        if(j == -1 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }
    //printf("ni-j = %d - %d = %dn",i,j,i-j);
    if(j == (int)strlen(t))
        return i-j;
    else
        return -1;
}
int mAIn()
{
    //char* str[] = {"ACBACAACAACACAACAB","ACAACAB"};
    //char* str[] = {"abaabaabeca","abaabe"};
    char* str[] = {"abaabaeabaabea","abaabe"};
    int *next = getNextArray(str[1]);
    int i,j;
    printf("主串s[]=    ");
    for(i=0;i<(int)strlen(str[0]);i++)
        printf("%c ",str[0][i]);
    printf("n");
    for(i=0;i<2;i++)
    {
        printf("模式串t[]=  ");
        for(j=0;j<(int)strlen(str[1]);j++)
            printf("%c ",str[1][j]);
        printf("n");
    }
    printf("next[]   = ");
    for(i=0;i<strlen(str[1]);i++)
        printf("%d ",next[i]);
    int n = kmpMatch(str[0],str[1]);
    printf("n模式串t首次匹配到主串s的位置:%dn",n);
    getchar();
}
/*
主串s[]=    a b a a b a a b e c a
模式串t[]=  a b a a b e
模式串t[]=  a b a a b e
next[]   = -1 0 0 1 1 2
模式串t首次匹配到主串s的位置:3

主串s[]=    A C B A C A A C A A C A C A A C A B
模式串t[]=  A C A A C A B
模式串t[]=  A C A A C A B
next[]   = -1 0 0 1 1 2 3
模式串t首次匹配到主串s的位置:11

主串s[]=    a b a a b a e a b a a b e a
模式串t[]=  a b a a b e
模式串t[]=  a b a a b e
next[]   = -1 0 0 1 1 2
模式串t首次匹配到主串s的位置:7

*/

demo JAVA code:

class Ideone
{
    public static int[] getNextArray(char[] t) {
        int[] next = new int[t.length];
        next[0] = -1;
        next[1] = 0;
        int k;
        for(int j = 2; j < t.length; j++) {
            k=next[j-1];
            while(k!=-1) {
                if(t[j - 1] == t[k]) {
                    next[j] = k + 1;
                    break;
                }
                else {
                    k = next[k];
                }
                next[j] = 0;  //当k==-1而跳出循环时,next[j] = 0,否则next[j]会在break之前被赋值
            }
        }
        return next;
    }
    
    /**
    * 对主串s和模式串t进行KMP模式匹配
    * @return 若匹配成功,返回t在s中的位置(第一个相同字符对应的位置),若匹配失败,返回-1
    */
    public static int kmpMatch(String s_arr, String t_arr){
        char[] s = s_arr.toCharArray();
        char[] t = t_arr.toCharArray();
        int[] next = getNextArray(t);
        for(int i=0;i<t.length;i++)
            System.out.print(next[i] + " ");
        int i = 0, j = 0;
        while(i<s.length && j<t.length){
            if(j == -1 || s[i]==t[j]){
                i++;
                j++;
            }
            else
                j = next[j];
        }
        System.out.printf("n%d %d %dn",i,j,t.length);
        if(j == t.length)
            return i-j;
        else
            return -1;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
        int n = kmpMatch("ACBACAACAACACAACAB","ACAACAB");
        System.out.printf("%dn",n);
	}
}
/*
-1 0 0 1 1 2 3 
18 7 7
11
*/


Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
诱导付费、自动扣费……微短剧被质疑借助算法精准“围猎”老年人
诱导付费、自动扣费、重复收费&hellip;&hellip;聚焦身边的消费烦心事⑦丨一些微短剧被质疑借助算法精准“围猎”老年人中工网北京3月31日电(工人日报&mdash;中工网记者刘兵)...【详细内容】
2024-04-01  Search: 算法  点击:(11)  评论:(0)  加入收藏
分析网站SEO快速排名算法对网站具体的影响效果
亲爱的朋友们,今天我想和大家分享一个我们都关心的话题&mdash;&mdash;网站SEO快速排名算法对网站我们身处一个信息爆炸的时代,如何在海量的信息中脱颖而出,成为了一个我们不得...【详细内容】
2024-03-28  Search: 算法  点击:(21)  评论:(0)  加入收藏
当prompt策略遇上分治算法,南加大、微软让大模型炼成「火眼金睛」
近年来,大语言模型(LLMs)由于其通用的问题处理能力而引起了大量的关注。现有研究表明,适当的提示设计(prompt enginerring),例如思维链(Chain-of-Thoughts),可以解锁 LLM 在不同领域的...【详细内容】
2024-03-12  Search: 算法  点击:(21)  评论:(0)  加入收藏
谷歌宣布更新搜索算法:打击AI生成内容,提高搜索结果质量
IT之家 3 月 6 日消息,谷歌于当地时间 5 日发文宣布,针对用户对搜索结果质量下降的反馈,将对算法进行调整,旨在打击 AI 生成的内容以及内容农场等垃圾信息,使用户能够看到更多“...【详细内容】
2024-03-06  Search: 算法  点击:(44)  评论:(0)  加入收藏
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  Search: 算法  点击:(18)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03  Search: 算法  点击:(54)  评论:(0)  加入收藏
简易百科之什么是搜索引擎的PageRank算法?
简易百科之什么是搜索引擎的PageRank算法?在互联网时代,搜索引擎是我们获取信息的重要工具。而PageRank算法则是搜索引擎的核心技术之一,它决定了网页在搜索结果中的排名。那么...【详细内容】
2024-01-24  Search: 算法  点击:(57)  评论:(0)  加入收藏
PageRank算法揭秘:搜索引擎背后的魔法师的工作原理
PageRank(PR)算法是由谷歌创始人之一的拉里&middot;佩奇LarryPage命名的一种衡量网站页面重要性的方法。根据谷歌的说法,PageRank通过计算页面链接的数量和质量来粗略估计分...【详细内容】
2024-01-23  Search: 算法  点击:(46)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  Search: 算法  点击:(46)  评论:(0)  加入收藏
百度最新的搜索引擎算法是什么样的?
百度搜索引擎算法是百度用来决定网页排名的算法。它是百度搜索技术的核心,也是百度作为全球最大的中文搜索引擎的基石。随着互联网的发展和用户需求的不断变化,百度搜索引擎算...【详细内容】
2024-01-10  Search: 算法  点击:(92)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(18)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(54)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(46)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(81)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(94)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(106)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(75)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(114)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(81)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(169)  评论:(0)  加入收藏
站内最新
站内热门
站内头条