KMP
字符串匹配算法:KMP学习心得
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。这周的数据结构课讲的是串，本以为老师会讲解KMP算法的，谁知到他直接略过了...没办法只能自己研究，这一琢磨就是3天，期间我都有点怀疑自己的智商...不过还好昨天半夜终于想明白了个中缘由，总结一些我认为有助于理解的关键点好了...
书上有的东西我就不说了，那些东西网上一搜一大片，我主要说一下我理解的由前缀函数生成的next数组的含义，先贴出求next数组的方法。
当一个字符串以0为起始下标时，next[i]可以描述为"不为自身的最大首尾重复子串长度"。
也就是说，从模式串T[0...i-1]的第一个字符开始截取一段长度为m(m < i-1)子串，再截取模式串T[0...i-1]的最后m个字符作为子串，如果这两个子串相等，则该串就是一个首尾重复子串。我们的目的就是要找出这个最大的m值。
例如:
若 i = 4 ，则 i - 1 = 3 ， m = next[4] = 2
从T[0...3]截取长度为2的子串，为"ab"
从T[0..3]截取最后2个字符，为"ab"
此时2个子串相等，则说明 next[4] = 2 成立，也可证明 m = 2 为最大的m值。
本来一开始我是没有加"不为自身"这个限制条件的，可是后来我发现一种情况:
若 i = 4 ，则 i - 1 = 3 ， m = next[4] = 3
从T[0...3]截取长度为3的子串，为"aaa"
从T[0..3]截取最后3个字符，为"aaa"
此时2个子串相等，则说明 next[4] = 3 成立。
但是我发现如果next[4] = 4：
从T[0...3]截取长度为4的子串，为"aaaa"
从T[0..3]截取最后4个字符，为"aaaa"
此时2个子串也是相等的，那么是不是说明 next[4] 应该等于4呢？
仔细观察后发现，如果 next[4] = 4 ，那么T[0...3]的前4个字符和后4个字符是重合的，并且重复子串和T[0...3]也是相等的。看过教材后发现教材中给出的前缀函数定义有一句为：next[j] = max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]'}，应该不包含子串为本身的情况...
这样再做PKU 2406 和 PKU 1961 的时候就很简单了，用 length - next[length] 求出"不为自身的最大首尾重复子串长度"，此时需要多求一位next[length]值（而next[length]刚好反映了lenght之前不为。。的长度），若最大重复子串的长度是length的非1整数倍，则证明字符串具有周期重复性质。
PKU 2752 是求 前缀 == 后缀的长度，也就是首尾重复子串长度，利用next数组记录的"不为自身的最大首尾重复子串长度"可以马上得到结果。
#include<iostream>
using namespace std;
int a[1000010],b[10010],next[10010];
int lena,lenb;
void inset()
{
int i;
scanf("%d%d",&lena,&lenb);
for(i=0;i<lena;i++)
scanf("%d",&a[i]);
for(i=0;i<lenb;i++)
scanf("%d",&b[i]);
}
void Gurm()
{
int j=0,k=-1;
next[0]=-1;
while(j<lenb)
{
if(k==-1 || b[j]==b[k])
{
++j;
++k;
next[j]=k;
}
else
{
k=next[k];
}
}
}
int kmp()
{
int i=0,j=0;
Gurm();
while(i<lena && j<lenb)
{
if(j==-1 || a[i]==b[j] )
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j<lenb) return -1;
else return i-j+1;
}
int main()
{
//freopen("D:\\in.txt","r",stdin);
int R;scanf("%d",&R);
while(R--)
{
inset();
printf("%d\n",kmp());
}
return 0;
}
KMP:next[]的应用。
* 一般next[i]与优化next[i]的区别：
*如果模式串p下标为i的字符（字符第一个的下标为0）的前k个字符与开头前k个字符相等（0=<k<i 注意这里没有等于i）
* 对于一般的next[i]，不管p[i]是否等于p[k+1]，next[i]都是等于k;
* 对于优化后的next[i]，如果p[i]不等于p[k+1],则next[i]=k,反之,next[i]=0.
* 这题的next[]是从0求到n,有n+1个值，因此对于next[i]=k的意义（0除外）就为：字符串下标为i的前k-1个字符与字符串头k个字符相等(上面提到的next[i]是与前k个字符与头k个字符相等next[i]才等于k)。
* 对于长度为i个字符串，i-next[i]（满足i % （i-next[i]）==0)代表的意义就是 长度为i的字符串 的 最小循环子串的长度
* 因此 字符串中存在周期的子串的最大循环次数=i/ (i-next[i]);
*
评论 (0)
