首页 > 试题广场 >

使用KMP算法在文本串S中找模式串P是一种常见的方法。假设S

[单选题]
使用KMP算法在文本串S中找模式串P是一种常见的方法。假设S=P={xyxyyxxyx}，亦即将S对自己进行匹配，匹配过程中正确的next数组是____。 
  • 0,1,1,2,2,1,2,2,3
  • 0,1,2,2,3,1,2,2,3
  • 0,1,1,2,3,1,2,2,3
  • 0,1,1,2,3,1,1,2,3
  • 0,1,2,2,3,1,1,2,3
  • 0,1,2,2,2,1,1,2,3
添加回答
推荐
时态的空白™头像 时态的空白™
1、首先求最大相同前缀后缀长度

模式串的各个子串

前缀

后缀

最大公共元素长度

x

空

空

0

xy

x

y

0

xyx

x ， xy

x ， yx

1 （ x ）

xyxy

x ， xy ， xyx

y ， xy ， yxy

2 （ xy ）

xyxyy

x ， xy ， xyx ， xyxy

y ， yy ， xyy ， yxyy

0

xyxyyx

x ， xy ， xyx ， xyxy ， xyxyy

x ， yx ， yyx ， xyyx ， yxyyx

1 （ x ）

xyxyyxx

x ， xy ， xyx ， xyxy ， xyxyy ， xyxyyx

x ， xx ， yxx ， yyxx ， xyyxx ， yxyyxx

1 （ x ）

xyxyyxxy

x ， xy ， xyx ， xyxy ， xyxyy ， xyxyyx ， xyxyyyxx

y ， xy ， xxy ， yxxy ， yyxxy ， xyyxxy ， yxyyxxy

2 （ xy ）

xyxyyxxyx

x ， xy ， xyx ， xyxy ， xyxyy ， xyxyyx ， xyxyyyxx ， xyxyyyxxy

x ， yx ， xyx ， xxyx ， yxxyx ， yyxxyx ， xyyxxyx ， yxyyxxyx

3 （ xyx ）

2、通过“最长相同前缀后缀长度值右移一位，然后初值赋为 -1 ”得到的 next 数组：

模式串

X

Y

X

Y

Y

X

X

Y

X

前缀最大公共元素

0

0

1

2

0

1

1

2

3

Next

-1

0

0

1

2

0

1

1

2

编辑于 2016-02-25 23:07:38 回复(17)
何止hz头像 何止hz
看到网上同一个字符串求 next 数组的值有两种，一种是 -1 开头，一种是 0 开头，虽然有差别，但是以 0 开头的next数组的每一项都比以 -1 开头的next数组的对应项大1，所以，具体是以 0 开头还是以 -1 开头看需要吧，算法都是一样的．KMP 的原始论文 （K，M，P 三个家伙写的原文）中是以 0 开头的。
发表于 2020-05-16 08:13:15 回复(0)
新世纪的神头像 新世纪的神
看了牛客网左神的视频，真正弄懂了kmp算法
发表于 2016-06-16 19:26:03 回复(1)
StrongYoung头像 StrongYoung

严版数据结构求 next 的公式：

我们主要观察第二项，存在两种情况：

（ 1 ）集合为空，若集合为空，则属于公式中的第一或第三种情况（其他情况）， j=1 的时候， next[1]=0 ，当 j>1 的时候， next[j]=1 。

（ 2 ）集合不为空，则我们要取的 k ，是集合中 k 的最大值。

K 需要满足两个条件，一是 1<k<j ，二是后面那个。
--------------------------------------------------------
对于前面这个，不用多说，对于后面这个，如果只看形式化的公式，估计比较难理解其意义。通过阮老师的博文（http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html），不难理解，后面这个表达式的意义就是所有前缀与所有后缀中，前缀与后缀相同的情况，那么，这个 k 的取值就是前缀与后缀相等时，字符串的长度加上 1 。
-------------------------------------------------------

先以严老师书上的例子：

求模式串 abaabcac 的 next 数组

当 j=1 时， next[1]=0 ，直接是公式的第一种情况

当 j=2 时，因为第二种情况要保证集合不为空且 1<k<j ，那么， j=2 时，集合为空，所以不符合第二种情况，因此，属于其他情况，即 next[2]=1

当 j=3 时， k 要小于 j ，所以，我们要在模式串找长度小于 j 的前面全部串的前缀与后缀相同时的最大长度，也就是在模式串中找到前两位 ab ，来找他们最长的前缀与后缀及长度，可以发现，他们没有相同的前缀与后缀，因此，长度为 0 ，而 k 等于长度加 1 ，所以 next[3]=1

当 j=4 时，在 aba 中找前缀与后缀的相同时的最大长度，可以求出最大长度Max为 1 ，所以 next[4]=2

当 j=5 时，在 abaa 中找，Max为 1 ，所以 next[5]=2

当 j=6 时，在 abaab 中找，Max为 2 ，所以 next[6]=3

当 j=7 时，在 abaabc 中找，Max为 0 ，所以 next[7]=1

当 j=8 时，在 abaabca 中找，Max为 1 ，所以 next[8]=2

 

之所以要找前缀与后缀，是因为我们在比较的时候，避免做多余的工作，即每次遇到主串和模式串不等时，都把模式串直接从头开始比。
-------------------------------------------------------------------

以模式串为 xyxyyxxyx 为例，求 next

当 j=1 ， next[1]=0

当 j=2 ， next[2]=1

当 j=3 ，在 xy 中找前缀与后缀，最大长度 max 为 0 ， next[3]=1

当 j=4 ，在 xyx 中找， Max 为 1 ， next[4]=2

当 j=5 ，在 xyxy 中找， Max 为 2 ， next[5]=3

当 j=6 ，在 xyxyy 中找， Max 为 0 ， next[6]=1

当 j=7 ，在 xyxyyx 中找， Max 为 1 ， next[7]=2

当 j=8 ，在 xyxyyxx 中找， Max 为 1 ， next[8]=2

当 j=9 ，在 xyxyyxxy 中找， Max 为 2 ， next[9]=3

 

编辑于 2015-09-14 11:04:36 回复(6)
厚德载物头像 厚德载物

解析：

首先求出最长公共元素长度 0 0 1 2 0 1 1 2 3

求出 next 数组 -1 0 0 1 2 0 1 1 2 KMP 应用 next 数组时，当第 j 个元素不匹配时，模式串右移 j-next[j] 个字符

当求出的 next 数组为 0 1 1 2 3 1 2 2 3 时， KMP 应用 next 数组时，当第 j 个元素不匹配时，模式串右移 j-1-next[j] 个字符

发表于 2015-08-25 00:38:25 回复(3)
Angelica头像 Angelica
http://wenku.baidu.com/view/892eb1fd0242a8956bece40d.html
这个文档的next数组解法非常详细，大家可以看一看
发表于 2016-04-02 02:54:34 回复(5)
青鸟WD头像 青鸟WD

KMP算法

next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。
next数组即为匹配串不对应后模式串改从哪一位开始继续比较，即移位后的模式串对应的比较子串符位置
为0则字符串右移一位，然后从0开始比较
如果为1即从第1个字符再开始比较
整个过程只遍历了字符串一次，做的只有在模式串之间比较并根据Next数组跳转比较
发表于 2017-10-02 14:48:15 回复(0)
CodeBunny头像 CodeBunny
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
这个老师对KMP解析的真心不错，简单易懂！！！
发表于 2020-09-27 16:49:41 回复(0)
七。小H头像 七。小H

KMP算法是字符串模式匹配的一个改进的算法，此算法可以 在O(m+n)的时间数量级上完成串的模式匹配操作。其主要是求next[]数组。我的这个见解只为了很快求出next[]数组，至于具体的代码实现，还是用经典的代码实现。

KMP算法的思想是当主串中的第i个字符与模式中的第j个字符“失配“（即比较不相等）时，主串中的第i个字符（i不回溯，当然是可以往前加1的）应与模式中的哪个字符比较。（这个可以先不理解，看完就懂啦）

举个例子：

j 1 2 3 4 5 6 7 8
模式串 a b a a b c a c
next[j] 0 1 1 2 2 3 1 2


next[j]就是找到p1p2......pj-1这个串中”最长的对称的字符串“。我是加引号的啊，不一定是你想的对称啊！

个人思想：

next[1]为0，next[2]为1，这是不用再算的，也是一定的。我们也没有必要再费心去算。我们从第三个开始。

 aba: 其前缀字符串是ab.我们所说的最长的对称子字符串是指这样的对称。如：ab  ab 。而不是类似这样的对称，

ab  ab  a。对，我想表达的意思就是第一个字符串中必须含有第一个字符，第二个字符串中必须含有最后一个字符。所以ab的最长的对称的字符串是0，所以我们的next[3]=0+1=1,对就是最长字符串加1。至于为什么是这样，我想表达一下，却发现很难用语言来说明（原谅我吧）

abaa:其前缀字符串是aba,按我们所说的对称标准，其最长的对称字符串的长度是1，所以其next[4]=1+1=2。

abaab:其前缀字符串是abaa,其最长的对称字符串长度也是1，所以其next[5]=1+1=2;

abaabc:其前缀字符串是abaab,其最长的对称字符串是前后的ab,所以其长度是2，所以next[6]=2+1=3;

abaabca:其前缀字符串是abaabc,是没有我们所说的对称的，所以是0，所以next[7]=0+1=1.注意：这里的p1p2=ab,p4p5=ab,这两个字符串不是我们所要的对称字符串。因为第二个字符串没有包含p6,即pj-1这个字符。

。。。。。。。。。。。。。


发表于 2015-11-16 23:05:02 回复(2)
牛客803828780号头像 牛客803828780号
第一位0 第二位1 第三位看前面最大匹配0 加上1结果是1 第四位最大匹配1结果是2 …… 最终结果011231223
发表于 2022-01-11 00:17:03 回复(0)
牛客473338572号头像 牛客473338572号
所以，选项里没一个对啊
发表于 2021-07-15 15:30:41 回复(0)
不做人了头像 不做人了
先求公共元素数组 但是为啥要由移动 
发表于 2020-05-28 19:24:09 回复(1)
codeor头像 codeor
给你们一个简单的方法求next数组！！！ 先把序列编号:123456789…… 对于前两个为0,1没问题，第三个:x前面一个为y，y对应的next数组下标为1，找到编号为1的(注意是编号)发现是x，与当前x前面的y不相等，故第三个x的next为1(此时已经到达首部)！！第四位:其前面一个为x，x的next下标为1，找到编号为1的字母，发现为x，与当前x为同一字母，故当前xnext为2，，(当前x前面y的next下标)1+1！！！依次类推
发表于 2019-08-03 21:40:49 回复(0)
EstelleDAI头像 EstelleDAI
kmp没懂
发表于 2019-04-04 21:53:02 回复(0)
牛客5536714号头像 牛客5536714号
前面不应该是012312234么
编辑于 2018-09-12 19:29:58 回复(0)
若只如初见201803011505196头像 若只如初见201803011505196
kmp算法我又忘了，我能说什么(ー_ー)!!
发表于 2018-07-30 16:01:20 回复(0)
lucky_me头像 lucky_me 
KMP 计算next数组的算法：
int[] next = new int[arr.length];
next[0] = -1;
next[1] = 0;
int pos = 2; int cn = 0;
while(pos<next.length)
{
if(arr[pos-1]==arr[cn])
{
    next[pos++] = next[cn];
}
else if(cn>0)
{
    cn = next[cn];
}
else{
    next[pos++] = 0;
}
}
发表于 2018-05-19 15:00:44 回复(0)
vegetablechicken头像 vegetablechicken
KMP版本太多了，我个人编程时P[0]不匹配，next[0]自然是-1，通过-1告诉程序T现在的头要往后走一位。不过既然选项都是next[0]==0，那只能都+1了。只是约定不一样而已。
发表于 2017-07-23 16:06:55 回复(0)
Blizard223头像 Blizard223 
//求next数组方法，注意这里的下标从0开始，所以next[0]=-1，计算出结果后，再每位+1。
void buildNext(string& s, int n)
{
	int k = -1;
	int j = 0;
    vector<int> next(n+1);
	next[0] = -1;
	while(j < n)
	{
		if(k == -1 || s[j] == s[k])
		{
			k ++;
			j ++;
			next[j] = k;
		}
		else
		{
			k = next[k];
		}
	}
}

编辑于 2016-08-21 10:48:33 回复(0)
stevenniu头像 stevenniu 
public static void makeNext(char P[], int next[]) {
		int q, k;// q:模版字符串下标；k:最大前后缀长度
		int m = P.length;// 模版字符串长度
		next[0] = 0;// 模版字符串的第一个字符的最大前后缀长度为0
		// for循环，从第二个字符开始，依次计算每一个字符对应的next值
		for (q = 1, k = 0; q < m; ++q) {
			// 递归的求出P[0]···P[q]的最大的相同的前后缀长度k
			while (k > 0 && P[q] != P[k]) {
				k = next[k - 1];
			}
			// 如果相等，那么最大相同前后缀长度加1
			if (P[q] == P[k]) {
				k++;
			}
			next[q] = k;
		}
		System.out.println(Arrays.toString(next));
	}
      求出最大公共字符串长度 0 0 1 2 0 1 1 2 3 
       求next函数的过程是一个递推的过程：
       1.首先由定义得next[0]=-1，next[1]=0;

2.假设已知next[j]=k，又T[j] = T[k]，则显然有next[j+1]=k+1；

3.如果T[j]!= T[k]，则令k=next[k]，直至T[j]等于T[k]为止。

注：

1.虽然next定义中没有明确指出next[1]=0，但由0<k<j的条件很容易判断出next[1]只能等于0；

2.next[j]=k表明在T串中的字符T[k]之前存在一个长度最大的子串"tj-ktj-k+1…tj-1"和T串中的子串 "t0t1…tk-1" 相等，而现在又知道了tj=tk，这就是说，在字符T[k+1]之前存在着一个长度最大的子串使得等式 "t0t1…tk"="tj-ktj-k+1…tj"成立，则根据next函数值的定义不就得到next[j+1]=k+1了吗？

3.由于tj!=tk，则等式"t0t1…tk"="tj-ktj-k+1…tj" 不成立，也就是说，在字符T[k+1]之前不存在一个子串" tj-ktj-k+1…tj"和子串"t0t1…tk"相等，那么是否可能存在另一个值p<k，使等式"t0t1…tp"=" tj-ptj-p+1…tj" 成立，这个p显然应该是 next[k]，因为这相当于一个"利用next函数值进行T串和T串的匹配"问题。

由此可得下列求 next 函数值的算法，它和上述的KMP算法非常相似。

所以可得next[]={ -1 0 0 1 2 0 1 1 2 }



编辑于 2015-09-07 16:08:59 回复(0)
提交观点

问题信息

查找
来自：数据分析工程师考试样卷
难度：
20条回答 15696浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号