如何用KMP算法高效匹配长尾词？

本文共计809个文字，预计阅读时间需要4分钟。

KMP算法是一种用于字符串匹配的算法，其核心思想是利用已知的部分匹配信息来避免不必要的比较，从而提高匹配效率。简单来说，KMP算法通过构建一个部分匹配表（也称为失败函数），来指示在发生不匹配时，字符串模式应该回溯多少个位置，然后再继续匹配。这种策略避免了每次不匹配都从头开始比较，大大提高了匹配速度。

KMP是用于字符串匹配的一种算法emmmmm完全不知道怎么讲理解了之后会发现思路挺好想的但是我用了一中午来理解正常的字符串匹配都是一位一位枚举但在某

 

 

KMP是用于字符串匹配的一种算法

emmmmm完全不知道怎么讲

理解了之后会发现思路挺好想的但是我用了一中午来理解

正常的字符串匹配都是一位一位枚举但在某些情况下复杂度太高

所以KMP算法应运而生

KMP是三个人的名字他们共同设计完成了这一算法【然而他们是谁www

这种算法在最坏情况下时间复杂度也为O(n);

那么KMP是怎么个思路呢

首先有一个文本串A一个子串B

要找到B在A中出现的位置

当我们从头枚举遇到不匹配的情况时本来应当从下一位再开始找

但是我们可以发现

像 A ACACBCABB

    B ACAB

再次比对的时候不需要从第二位的C开始直接从第三位的A开始不是更方便吗

KMP的重点就在于在匹配过程中当匹配失败后从已匹配过的重复的字符串开始下一次比对

那么如何实现呢

啊啊啊好难讲想放弃嗷

 放弃

我还是直接放代码吧orz

在注释里讲好了

完全不会讲啊【丧

我大概是假的理解了吧

 

#include#includeusing namespace std;#define maxn 1000010char l[maxn],s[maxn];int nxt[maxn];int main() {scanf("%s%s",l 1,s 1);//从第一位开始输int lenl strlen(l 1);int lens strlen(s 1);int k 0;//k记录当前字符能与某前缀匹配子串自己匹配自己nxt[1] 0;//第一个字符显然没有与之匹配的for(int i 2; i < lens; i) {//从第二位开始比对while(k s[k 1])//失配跳到之前匹配的地方k nxt[k];if(s[i] s[k 1])//匹配k;nxt[i] k;}k 0;//k记录匹配到第几位子串和文本串匹配for(int i 1; i < lenl; i) {while(k s[k 1])//失配跳到匹配的前缀处KMP算法精华所在k nxt[k];if(l[i] s[k 1])k;if(k lens)printf("%d\n",i - lens 1);}for(int i 1; i < lens; i)printf("%d ",nxt[i]);//题目要求orzreturn 0;}

【瘫

【我说的也太烂了吧喵的我讲什么了吗

【实名最水

 三天之后觉得自己太丧于是准备再写写orz

emmmm

怎么说KMP算法自己匹配自己是精华所在也是比较不好理解的地方

尝试讲讲吧

一个字符串

abcabcd

当你从头开始比对匹配到第七位即d时失配了

这样你下一次开始匹配一定不是从第二位开始匹配

很明显我们可以看出第一到第三位与第四到第六位是一样的

我们下次匹配就从第四位开始

那么这样自己匹配自己就是看失配的位置的最长后缀能匹配到的前缀长度

emmm讲的乱七八糟orz

KMP真的挺不好理解的对于本蒟蒻来说

我用了一晚上加一中午理解到现在还讲不明白QAQ

希望大家能找到自己能看懂的题解学会KMP  orz

转:www.cnblogs.com/sevenyuanluo/p/10065352.html