它是什么 某例题 知识储备如何产生next数组?我来解释一下尾声

你可能觉得我在扯淡.昨天还在讲省选内容网络流的我今天搞起普及内容KMP来了. 可是这是真的,最大流dinic加当前弧优化我两天就把模板背出来了,kmp搞了我半年我还是不懂这个next数组是怎么来的. 所以我今晚用1个小时40分钟给自己讲解一下kmp算法.

它是什么

首先你需要知道的是它是一个字符串匹配算法. 看例题.luogu p3375 [模板]kmp字符串匹配

某例题

题目描述 如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。 为了减少骗分的情况，接下来还要输出子串的前缀数组next。 （如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。） 输入输出格式 输入格式： 第一行为一个字符串，即为s1 第二行为一个字符串，即为s2 输出格式： 若干行，每行包含一个整数，表示s2在s1中出现的位置 接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。 (以上摘自题目描述)

好.那么给出长度均为1e6的两个字符串s1,s2,求s2在s1中出现了几次,并输出每一个出现的位置. 接下来还要输出一行next数组.

知识储备

我看了半年kmp,愣是一点没看懂.洛谷上面我是手打别人的代码A掉的. 首先你不可能不会暴力匹配吧. 假设有这两个串.

abbacdbacdbcdcbdabcdcbacbdacbdacbdacbdacd abcdcba | | ...... | | abcdcba 显然暴力匹配会把下面字符串的第一位与上面的某一位对齐,然后一位一位去看. 如果失配,我们会把下面字符串向右移动一位,再重新匹配. 这样的话显然效率会非常低,很多时候本来后面一位就不可能匹配.

因此有了这个算法.这个算法在匹配的时候可以一次将s2向右移很多位,从而避免不必要的匹配. 那么为什么可以一次移很多位呢?这是根据下面的那个字符串的性质决定的.

这样的话需要牵扯到一些非常重要的知识:前缀,后缀. 那我就当你们都知道了. 我们定义next[i]数组是字符串到i位时该子串的前缀和后缀的最大相同长度. 考虑字符串abcdabc.对于前4位来讲,都是0. 对于后面三位来讲. next[5],abcda. 显然前缀和后缀的最大相同长度是1,即"a"这个子串. next[6],abcdab,长度2. next[7],abcdabc,长度是3. 因此next数组就是0,0,0,0,1,2,3.

这样比如说当字符串在第7位失配了.

s="abcdabdabcdabc" t="abcdabc" 显然开始匹配的时候在第7位失配了. 这个时候移到哪里呢? 向后移动xxxx位.//然而我不知道移多少位 那么移动完之后就变成这样了. abcdabdabcdabc abcdabc 非常快.

如何产生next数组?

我们上代码.这个代码不是我的,是某巨佬的,我写的不能看. 代码把匹配的部分也放进去了.

#include<cstdio> #include<cstring> #define N 1000005 char s[N],t[N];//首先你要知道的是,我们要在t串中找到s串. int p[N],i,j,n,l; int main() { scanf("%s%s",t+1,s+1); n=strlen(s+1),l=strlen(t+1);//记录两串之长. p[0]=-1;//将next[0]初始化为-1表示不存在,用以当j为0的时候可以跳出循环 for(i=1,j=-1;i<=n;++i) { for(;j>=0&&s[i]!=s[j+1];) j=p[j];//关键就在于为什么j=p[j]. p[i]=++j; }j=1; for(i=1;i<=l;++i) { for(;j>=0&&t[i]!=s[j+1];) j=p[j]; ++j; if(j==n) { printf("%d\n",i-n+1); j=p[j]; } } for(i=1;i<=n;++i) printf("%d ",p[i]); }

我来解释一下

所谓next数组,其实就是s串自己对自己进行kmp匹配的结果. 首先你可以知道的是,假设我们在算出next[i]之前已经知道了next[1],next[2],next[3],……,next[i-1]的值,我们怎么求出next[i]呢?

现在next[i]=++j,i++. 那么目前来说s[i-1]=s[j](因为上一次循环保证),如果s[i]=s[j+1],很明显答案就直接+1了.这个不用解释吧. 如果s[i]!=s[j+1],那么我们需要找到之前的一个j,使得s[i]=s[j+1].这个j怎么找呢? 朴素的方法,while(s[i]!=s[j+1]) j--;好,我建议你选择暴力. 那么还有什么办法呢?注意next数组的特性,最长前缀后缀的相同长度. 当s[i]!=s[j+1],我们可以直接跑到算出来的前缀里面找,直到找到一个前缀,使得s[i]=s[j+1]. 这样就有了j=next[j].当然在实际匹配的时候也就这样了.

如果你还不会,背代码吧.kmp所用的范围比较窄,基本也只有字符串匹配这一种用法. 再往后exkmp?不存在的!直接上自动机!!!!!!

尾声

没想到1个小时就写完了.我自己大概是懂了.可是真的吗? 我把我奇丑代码放在这里.

#include<bits/stdc++.h> using namespace std; const int tamate=1e6; char s[tamate|10],t[tamate|10]; int p[tamate|15]={-1},n,l; int main() { int i,j; scanf("%s%s",t+1,s+1); n=strlen(s+1),l=strlen(t+1); for (i=1,j=-1;i<=n;p[i++]=++j) for (;~j&&s[i]!=s[j+1];j=p[j]); for (i=j=1;i<=l;++i) { for (;~j&&t[i]!=s[j+1];j=p[j]); if (++j==n) printf("%d\n",i-n+1),j=p[j]; } for (i=1;i<=n;++i) printf("%d ",p[i]); }