KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
这周的数据结构课讲的是串，本以为老师会讲解KMP算法的，谁知到他直接略过了...没办法只能自己研究，这一琢磨就是3天，期间我都有点怀疑自己的智商...不过还好昨天半夜终于想明白了个中缘由，总结一些我认为有助于理解的关键点好了...
书上有的东西我就不说了，那些东西网上一搜一大片，我主要说一下我理解的由前缀函数生成的next数组的含义，先贴出求next数组的方法。
void GetNext(char* t, int* next)
{
int i, j, len;
i = 0;
j = -1;
next[0] = -1;
while(t[i] != '\0')
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
当一个字符串以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]值，若最大重复子串的长度是length的非1整数倍，则证明字符串具有周期重复性质。
PKU 2752 是求 前缀 == 后缀 的长度，也就是首尾重复子串长度，利用next数组记录的"不为自身的最大首尾重复子串长度"可以马上得到结果。
#include <string>
#include <iostream>
using namespace std;
const int maxn=1000005;
char a[maxn];
int next[maxn];
int len;
void Cal_Next(char str[],int next[],int str_len)
{
next[0]=-1;//next[i]=j,表示 str[0..j]=str[i-j..i]
int j=next[0];
for(int i=1;i<str_len;i++)
{
while(j>=0&&str[i]!=str[j+1]) j=next[j];
if(str[i]==str[j+1]) j++;
next[i]=j;
}
}
//void STR_Find_KMP(char main_str[],char sub_str[],int next[])
//{
// int j=next[0];
// for(int i=1;i<len;i++)
// {
// while(j>=0&&main_str[i]!=sub_str[j+1]) j=next[j];
// if(main_str[i]==sub_str[j+1]) j++;
// if(j>=0&&(i+1)%(i-j)==0)
// {
// printf("%d %d\n",i+1,(i+1)/(i-j));
// }
// }
//}
int main()
{
int t=0,j;
while(scanf("%d",&len)&&len!=0)
{
t++;
scanf("%s",a);
printf("Test case #%d\n",t);
Cal_Next(a,next,len);
for(int i=1;i<len;i++)
{
j=i-next[i];
if((i+1)%j==0&&next[i]!=-1) printf("%d %d\n",i+1,(i+1)/j);
}
printf("\n");
}
return 0;
}
按照算法导论上写的版本：
//模式匹配,kmp算法,复杂度O(m+n)
//返回匹配位置,-1表示匹配失败,传入匹配串和模式串和长度
//可更改元素类型,更换匹配函数
#define MAXN 10000
#define _match(a,b) ((a)==(b))
typedef char elem_t;
int pat_match(int ls,elem_t* str,int lp,elem_t* pat){
int fail[MAXN]={-1},i=0,j;
for (j=1;j<lp;j++)
{
for (i=fail[j-1];i>=0&&!_match(pat[i+1],pat[j]);i=fail[i]);
fail[j]=(_match(pat[i+1],pat[j])?i+1:-1);
}
for (i=j=0;i<ls&&j<lp;i++)
if (_match(str[i],pat[j]))
j++;
else if (j)
j=fail[j-1]+1,i--;
return j==lp?(i-lp):-1;
}
class Match
{
public:
Match(): repos(NULL){}
Match(const string& main, const string& mod)
:repos(new int[mod.size()]), m_main(main), m_mod(mod)
{}
~Match()
{
delete [] repos;
}
//~ kmp搜索，默认从主串0位置处开始，
//~ 匹配成功返回匹配开始的索引，否则返回-1
int strkmp(size_t pos = 0);
//~ 重设主串与模式串
void reset(const string& main, const string& mod);
private:
int * repos;
string m_main; //~ 主串
string m_mod; //~ 模式串
//~ 生成重定位的索引值
void gen_rps();
};
void Match::gen_rps()
{
repos[0] = -1;
int i = 0, j = -1;
while(i < (int)m_mod.size()-1)
{
if( j == -1 || m_mod[i] == m_mod[j])
{
++i;++j;
repos[i] = j;
}
else
j = repos[j];
}
}
int Match::strkmp(size_t pos)
{
gen_rps();
int i = (int)pos, j = 0;
while(i < (int)m_main.size() && j < (int)m_mod.size())
{
if(j == -1 || m_main[i] == m_mod[j])
{
++i;++j;
}
else
j = repos[j];
}
if(j == m_mod.size())
return i - (int)m_mod.size();
else
return -1;
}
void Match::reset(const string& main, const string& mod)
{
// ~Match(); 为什么不让我显式调用析构函数
delete [] repos;
m_main = main;
m_mod = mod;
repos = new int[mod.size()];
}
int main()
{
Match match("acabaabaabcacaabc", "abaabcac");
cout<<match.strkmp(3)<<endl;
return 0;
}