一.清华殷人昆数据结构笔记（C＋＋版，ppt格式）：
1.失效函数f(j)
f(j)=
max{k|0<=k<j and p[0]p[1]...p[k]=p[j-k]p[j-k+1]...p[j]}的最大整数
-1 其他情况
2.利用失效函数f(j)的匹配处理
如果 j = 0，则目标指针加 1，模式指针回到 p[0]。
如果 j > 0，则目标指针不变，模式指针回到 p[f(j-1)+1]。 <?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
二.用c++语言描述算法的讲稿(清华的严蔚敏）、刘宇数据结构：
1.Next[j]
Next[j] =
0 j=1
max{k|1<k<j and p[1]p[2]...p[k-1]=p[j-k+1]p[j-k+2]...p[j-1]}
1 其他情况
三.总结
1.首先排除起始下标为0和1带来的混淆。
起始下标为0：
f(j)=
max{k|0<=k<j and p[0]p[1]...p[k]=p[j-k]p[j-k+1]...p[j]}的最大整数
-1 其他情况
Next[j] =
-1 j=0
max{k|0<k<j and p[0]p[2]...p[k-1]=p[j-k]p[j-k+1]...p[j-1]}
0 其他情况
起始下标为1：
f(j)=
max{k|0<=k<j and p[1]p[2]...p[k]=p[j-k＋1]p[j-k+2]...p[j]}的最大整数
0 其他情况
Next[j] =
0 j=1
max{k|1<k<j and p[1]p[2]...p[k-1]=p[j-k+1]p[j-k+2]...p[j-1]}
1 其他情况
2.起始下标为1时，Next[1]=0，Next[2]=1。
3.结论
f(j)的值是为j+1位置失配时跳转做准备，当j+1位置失配时，跳转到f(j)+1。
Next[j]的值直接为j位置失配时跳转做准备，当j位置失配时，跳转到Next[j]。
所以，Next[j]=f(j-1)+1。
4.例子（起始下标为1）
| Position |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| Value |
a |
b |
a |
a |
b |
c |
a |
c |
| Next[j] |
0 |
1 |
1 |
2 |
2 |
3 |
1 |
2 |
| f(j) |
0 |
0 |
1 |
1 |
2 |
0 |
1 |
0 |
5.代码
void setFail( const char *szFind, int *arFail )
{
int nLenFind = strlen(szFind);
int i,j;
i = 0;
arFail[i] = -1;
j = arFail[i];
i ++;
j ++;
while( i < nLenFind )
{
if( szFind[i] == szFind[j] )
{
arFail[i] = j;
i ++;
j ++;
}
else if( (szFind[i] != szFind[j]) && (j == 0) )
{
arFail[i] = -1;
i ++;
j = 0;
}
else if( (szFind[i] != szFind[j]) && (j != 0) )
{
//j --;
j = arFail[j-1]+1; //improvement
}
}
}
void setNext( const char *szFind, int *arNext )
{
int nLenFind = strlen(szFind);
int i,j;
i = 0;
arNext[i] = -1;
j = arNext[i];
while( i < nLenFind )
{
if( j == -1 )
{
arNext[i+1] = 0;
i ++;
j ++;
}
if( szFind[i] == szFind[j] )
{
arNext[i+1] = j + 1;
i ++;
j ++;
}
else if( szFind[i] != szFind[j] )
{
//j --;
j = arNext[j]; //improvement
}
}
}