神马文学网KMP算法
来源：百度文库 编辑：神马文学网 时间：2024/04/28 15:32:25
KMP算法
提示:在本文中i是主串下标,j是模式串下标
!!!!!如果你只想弄明白算法,请跳过理论分析,理论分析是我们在处理一个问题时的思想路线
一 理论论述：
（1）我们在求主串的匹配位置的时候，可以用游标卡尺的模型，即相对移动来思维，当找到匹配时或者是游标到底时游标停止移动，而移动越快，则耗时越短，而i就是主标，j就是游标；
（2）关于为什么要求next[j]
大家知道子串与模式串失配时，一定前边所比较过的一定匹配，即有"S[i-j+1],S[i-j+2],...S[i-1]"="T[1],T[2],...T[j-1]",在这个时候，我们一定要找出在不遗漏可能的匹配串条件下,子串相对于主串所能移动的最大元素个数，也等效于找出next[j]；
（3）求next[j]本意是找出应当和当前失配标度i(主尺标度）所指S[i]所比较的模式串的标度next[j]（游尺标度）所指的T[next[j]]，而要做到这一点，只要找出next[j]即可；
（4）求出k=next[j]，相当与模式串相对于主串前进（j-k）个元素；
（5）关于如何求next[j] 普通算法
核心是充分利用已经知道的信息，我们知道我们人（即古典算法）在看最多能移动多少长度时，一定是先拿T[1]和从S[i-j+1]开始起的元素进行比较，找到相同的再比较下个，由于目前所知道信息不包括S[i]（其实失配时，还是获得信息,在改进算法中就利用到了这一点）以及其以后的元素，一定无法利用，也就是说如果存在移动最大长度时，一定有"T[1],T[2],...,T[k-1]"="S[i-k+1],S[i-k+2],...,S[i-1]}"也就是
“将Next[j]解释为p1 p2 …… pj 中最大相同前缀子串和后缀子串（真子串）的长度较容易理解。
提供一个Next[j]的计算方法：
当j=1时，Next[j]=0；
当j>1时，Next[j]的值为模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1，无首尾相同的子串时 Next[j]的值为1。”
（引用自青玉案的《KMP》） 。
具体的求法书上有介绍,这个我只补充一点:我觉得书上所说求模式串与其自身匹配位置太过抽象,尽管本质确实如此,下边我会有更具体的方式.
(6)关于求next[j]的改进算法
其实本改进算法中唯一添加了的就是一个判断语句,它的核心正如上边所提到的,在于利用了求nextval[j]时,nextval[j]一定失配;并且将利用的工作引入准备工作---求nextval[].
二 算法分析
（1）Get_next普通算法
void get_next(SString T,int &next[])
{
j=1;next[1]=0;n=0;
//j也就是游标，而本算法中n则有两种含义A:判断游标i是否移动的标志；B:上次循环所求的next[]的值，
在这里next[0]存储的是长度，不予考虑，然后next[1]显然是0,n在此处则取A义。
while(j
{
if(n==0||T[j]==T[n])
//当找到next[j] 时移动游标，除了第一次循环是为方便算法的写法移动之外。
{
++j;++n;next[j]=n;
//当移动游标的时候，对next[j]赋值,至于n的自增在下边说明.
}
else n=next[n];
}
//我们以if语句的执行作为一次运算结束的标志,而上次运算所求出的假设为n1=next[j1],在这个时候进入下个循环有三种情况
①n1=0,在本普通算法中这只有在第一次循环时才可能出现,这个时候求的是T[2],我们知道这个时候应当无条件的把上个T[1]拿下来进行和主串中当前失配位置S[i]进行比较,就是说n2=1,亦n2=n1+1;
②n1!=0并且T[j1]=T[n1],显然这个时候所求next[j2]比上次多1,n2=n1+1;
③n1!=0并且T[j1]!=T[n1]那么这个时候就按照理论对上个n1求next[n1]尝试缩短"p1 p2 …… pj 中最大相同前缀子串和后缀子串（真子串）的长度",当然这里的缩短必须满足"T[1],T[2],...,T[k-1]"="S[i-k+1],S[i-k+2],...,S[i-1]"(这里只是抽象说法),这个时候再看看有没有n1=0或者T[j1]==T[n1],如果没有再求下一个next[n1],一直到最后出现
A:T[n1]=T[j1]则n2=n1+1,对next[j2]赋值,并进入求下个next[j3];
B:n1=0,这个时候我们知道没有任何 "T[1],T[2],...,T[n1-1]=S[i-n1+1],S[i-n1+2],...,S[j1-1]"是满足条件的,而T[j1]=T[1]是有可能的,将这个判别工作留给调用函数,直接从T[1]比较,也就是说n2=1,n2=n1+1.
}
//其实在本算法中有许多冗余之处,不过是为了下个改进算法而造成的
(2)Get_next改进算法
//这个才是实际运用的next[]算法
status Get_nextval(SString T,int &nextval[])
{
j=1; nextval[1]=0;n=0;
while(j
{
if(n==0||T[j]==T[n])
{
++j; ++n;
if(T[j!]=T[n]) nextval[j]=n;
else nextval[j]=nextval[n];//注意这里,直接把值给赋进去了,由于没有经过循环语句,n也没有自增;
}
else n=nextval[n];
}
}
//这个算法不过是判断了一下最后当前失配的T[j2]是否等于T[n2],然后再根据不同情况进行操作而已
我们还是以每次j的自增作为一个运算结束的标志,假设上次的j为j1,n为n1,那么这次时候所求为n2=next[j2]
①n1为0,这个时候我们知道没有任何 "T[1],T[2],...,T[n1-1]=S[i-n1+1],S[i-n1+2],...,S[j1-1]"是满足条件的,而T[j1]=T[1]是有可能的,再比较一下T[j2]和T[n2],如果不等,当然有n2=1,就是n2=n1+1;反之,则表示任何一个T[j2]以及其之前的元素都不适合拿来和主串比较,这个时候需要把主标i++,游标j++,而这个信息就以next[j2]=0来表达在调用函数中,也就是说next[j2]=next[1]=next[n1+1];
②略(同上,只是加一个判断)
③略
作者:天蓝色的鱼
完成于2003.11.9
声明:本文版权归天蓝色的鱼所有,任何用于以盈利为目的的行为必须经过作者授权方可
(此帖由天蓝色的鱼在2003-11-09.16:27:54编辑过)
(此帖由天蓝色的鱼在2003-11-20.22:21:31编辑过) #日志日期：2005-10-7 星期五(Friday) 晴
评论人：傻子曰 评论日期：2005-10-7 11:09
假设文本串“t1,t2,…tn”, 模式串为“p1,p2,…pn”,当文本串中的第I个字符与模式中第j个字符不匹配时，文本串的第i个字符再与模式串中的第k个字符进行比较，则模式中前k-1个字符的子串必须满足下面的关系式：’p1,p2…pk-1’=’pj-k+1,pj-k+2…pj-1
若令next[j]=k, 则next[j]表明当模式中第j个字符与文本串中相应字符不匹配时，在模式中需要从新和文本串中该字符进行比较的字符的位置。
next[j]=0，当j=1时
next[j]=max，{k｜1next[j]=1,其他情况
此时，kmp算法如下：
1）假设以指针i和j 分别指示文本串和模式串中的比较字符，令i和j的初值为1，开始匹配
2）若在匹配过程中ti=pj, 则i和j分别增1
3）若不相等，匹配失败后，则I不变，j退到next[j]位置在进行比较
4）若相等，则指针各增1，否则j再退到下一个next值的位置
5）依此类推，直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1，继续进行匹配；另一种是j退到值为0（即模式的第一个字符失配），则i和j也分别增1，表明从文本串的狭义个字符起和模式串重新开始匹配。
看它前面是否有一个最长的 "字符串"和从第一个字符开始的 "字符串" 相等， 若一个都没有就为1;如果有，你就把它找出来，看它有多长；next就是其长度加1
比如 模式是 "abaabcac" 的 next[j];
1.a 一定是 0 //第一个
2.b 一定是 1
3.为a,前一个为b,b != a(a为第一个字符),所以next[a] = 1;
4.为a,前一个为a,a == a,相等就再看ab != ba,所以next[a] = 2;(1+1）
5.为b,同上理有a==a,相等就再看ab != aa,所以next[b] = 2;(1+1)
6.为c,前一个为c, b!=a,ab==ab，所以next[c] = 3;(2+1)
7.为a,都没有相等的,所以next[a] = 1;
8.为c,a==a,所以next[c] = 2
next[j]=01122312
提示:在本文中i是主串下标,j是模式串下标
!!!!!如果你只想弄明白算法,请跳过理论分析,理论分析是我们在处理一个问题时的思想路线
一 理论论述：
（1）我们在求主串的匹配位置的时候，可以用游标卡尺的模型，即相对移动来思维，当找到匹配时或者是游标到底时游标停止移动，而移动越快，则耗时越短，而i就是主标，j就是游标；
（2）关于为什么要求next[j]
大家知道子串与模式串失配时，一定前边所比较过的一定匹配，即有"S[i-j+1],S[i-j+2],...S[i-1]"="T[1],T[2],...T[j-1]",在这个时候，我们一定要找出在不遗漏可能的匹配串条件下,子串相对于主串所能移动的最大元素个数，也等效于找出next[j]；
（3）求next[j]本意是找出应当和当前失配标度i(主尺标度）所指S[i]所比较的模式串的标度next[j]（游尺标度）所指的T[next[j]]，而要做到这一点，只要找出next[j]即可；
（4）求出k=next[j]，相当与模式串相对于主串前进（j-k）个元素；
（5）关于如何求next[j] 普通算法
核心是充分利用已经知道的信息，我们知道我们人（即古典算法）在看最多能移动多少长度时，一定是先拿T[1]和从S[i-j+1]开始起的元素进行比较，找到相同的再比较下个，由于目前所知道信息不包括S[i]（其实失配时，还是获得信息,在改进算法中就利用到了这一点）以及其以后的元素，一定无法利用，也就是说如果存在移动最大长度时，一定有"T[1],T[2],...,T[k-1]"="S[i-k+1],S[i-k+2],...,S[i-1]}"也就是
“将Next[j]解释为p1 p2 …… pj 中最大相同前缀子串和后缀子串（真子串）的长度较容易理解。
提供一个Next[j]的计算方法：
当j=1时，Next[j]=0；
当j>1时，Next[j]的值为模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1，无首尾相同的子串时 Next[j]的值为1。”
（引用自青玉案的《KMP》） 。
具体的求法书上有介绍,这个我只补充一点:我觉得书上所说求模式串与其自身匹配位置太过抽象,尽管本质确实如此,下边我会有更具体的方式.
(6)关于求next[j]的改进算法
其实本改进算法中唯一添加了的就是一个判断语句,它的核心正如上边所提到的,在于利用了求nextval[j]时,nextval[j]一定失配;并且将利用的工作引入准备工作---求nextval[].
二 算法分析
（1）Get_next普通算法
void get_next(SString T,int &next[])
{
j=1;next[1]=0;n=0;
//j也就是游标，而本算法中n则有两种含义A:判断游标i是否移动的标志；B:上次循环所求的next[]的值，
在这里next[0]存储的是长度，不予考虑，然后next[1]显然是0,n在此处则取A义。
while(j
{
if(n==0||T[j]==T[n])
//当找到next[j] 时移动游标，除了第一次循环是为方便算法的写法移动之外。
{
++j;++n;next[j]=n;
//当移动游标的时候，对next[j]赋值,至于n的自增在下边说明.
}
else n=next[n];
}
//我们以if语句的执行作为一次运算结束的标志,而上次运算所求出的假设为n1=next[j1],在这个时候进入下个循环有三种情况
①n1=0,在本普通算法中这只有在第一次循环时才可能出现,这个时候求的是T[2],我们知道这个时候应当无条件的把上个T[1]拿下来进行和主串中当前失配位置S[i]进行比较,就是说n2=1,亦n2=n1+1;
②n1!=0并且T[j1]=T[n1],显然这个时候所求next[j2]比上次多1,n2=n1+1;
③n1!=0并且T[j1]!=T[n1]那么这个时候就按照理论对上个n1求next[n1]尝试缩短"p1 p2 …… pj 中最大相同前缀子串和后缀子串（真子串）的长度",当然这里的缩短必须满足"T[1],T[2],...,T[k-1]"="S[i-k+1],S[i-k+2],...,S[i-1]"(这里只是抽象说法),这个时候再看看有没有n1=0或者T[j1]==T[n1],如果没有再求下一个next[n1],一直到最后出现
A:T[n1]=T[j1]则n2=n1+1,对next[j2]赋值,并进入求下个next[j3];
B:n1=0,这个时候我们知道没有任何 "T[1],T[2],...,T[n1-1]=S[i-n1+1],S[i-n1+2],...,S[j1-1]"是满足条件的,而T[j1]=T[1]是有可能的,将这个判别工作留给调用函数,直接从T[1]比较,也就是说n2=1,n2=n1+1.
}
//其实在本算法中有许多冗余之处,不过是为了下个改进算法而造成的
(2)Get_next改进算法
//这个才是实际运用的next[]算法
status Get_nextval(SString T,int &nextval[])
{
j=1; nextval[1]=0;n=0;
while(j
{
if(n==0||T[j]==T[n])
{
++j; ++n;
if(T[j!]=T[n]) nextval[j]=n;
else nextval[j]=nextval[n];//注意这里,直接把值给赋进去了,由于没有经过循环语句,n也没有自增;
}
else n=nextval[n];
}
}
//这个算法不过是判断了一下最后当前失配的T[j2]是否等于T[n2],然后再根据不同情况进行操作而已
我们还是以每次j的自增作为一个运算结束的标志,假设上次的j为j1,n为n1,那么这次时候所求为n2=next[j2]
①n1为0,这个时候我们知道没有任何 "T[1],T[2],...,T[n1-1]=S[i-n1+1],S[i-n1+2],...,S[j1-1]"是满足条件的,而T[j1]=T[1]是有可能的,再比较一下T[j2]和T[n2],如果不等,当然有n2=1,就是n2=n1+1;反之,则表示任何一个T[j2]以及其之前的元素都不适合拿来和主串比较,这个时候需要把主标i++,游标j++,而这个信息就以next[j2]=0来表达在调用函数中,也就是说next[j2]=next[1]=next[n1+1];
②略(同上,只是加一个判断)
③略
作者:天蓝色的鱼
完成于2003.11.9
声明:本文版权归天蓝色的鱼所有,任何用于以盈利为目的的行为必须经过作者授权方可
(此帖由天蓝色的鱼在2003-11-09.16:27:54编辑过)
(此帖由天蓝色的鱼在2003-11-20.22:21:31编辑过) #日志日期：2005-10-7 星期五(Friday) 晴
假设文本串“t1,t2,…tn”, 模式串为“p1,p2,…pn”,当文本串中的第I个字符与模式中第j个字符不匹配时，文本串的第i个字符再与模式串中的第k个字符进行比较，则模式中前k-1个字符的子串必须满足下面的关系式：’p1,p2…pk-1’=’pj-k+1,pj-k+2…pj-1
若令next[j]=k, 则next[j]表明当模式中第j个字符与文本串中相应字符不匹配时，在模式中需要从新和文本串中该字符进行比较的字符的位置。
next[j]=0，当j=1时
next[j]=max，{k｜1
此时，kmp算法如下：
1）假设以指针i和j 分别指示文本串和模式串中的比较字符，令i和j的初值为1，开始匹配
2）若在匹配过程中ti=pj, 则i和j分别增1
3）若不相等，匹配失败后，则I不变，j退到next[j]位置在进行比较
4）若相等，则指针各增1，否则j再退到下一个next值的位置
5）依此类推，直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1，继续进行匹配；另一种是j退到值为0（即模式的第一个字符失配），则i和j也分别增1，表明从文本串的狭义个字符起和模式串重新开始匹配。
看它前面是否有一个最长的 "字符串"和从第一个字符开始的 "字符串" 相等， 若一个都没有就为1;如果有，你就把它找出来，看它有多长；next就是其长度加1
比如 模式是 "abaabcac" 的 next[j];
1.a 一定是 0 //第一个
2.b 一定是 1
3.为a,前一个为b,b != a(a为第一个字符),所以next[a] = 1;
4.为a,前一个为a,a == a,相等就再看ab != ba,所以next[a] = 2;(1+1）
5.为b,同上理有a==a,相等就再看ab != aa,所以next[b] = 2;(1+1)
6.为c,前一个为c, b!=a,ab==ab，所以next[c] = 3;(2+1)
7.为a,都没有相等的,所以next[a] = 1;
8.为c,a==a,所以next[c] = 2
next[j]=01122312