UC知道BM算法好后缀问题
来源：百度知道 编辑：UC知道 时间：2024/06/06 05:31:35
下面是一段BM算法中的好后缀规则的代码。在while循环中pptr--好像没用到，一直搞不明白，while循环是如何实现找出移动的距离的。懂的指点一下吧~~
int* MakeShift(char* ptrn,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
char c;
if(shift == NULL)
{
printf("malloc failed!");
return 0;
}
c = *(ptrn + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它
*sptr = 1;//以最后一个字符为边界时，确定移动1的距离
pptr--;//边界移动到倒数第二个字符
while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;
//该do...while循环完成以当前pptr所指的字符为边界时，要移动的距离
do{
while(p1 >= ptrn && *p1-- != c);//该空循环，寻找与最后一个字符c匹配的字符所指向的位置
p2 = ptrn + pLen - 2;
int* MakeShift(char* ptrn,int pLen)
{
//为好后缀表申请pLen个int的空间
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便给好后缀表进行赋值的指标
char *pptr = ptrn + pLen - 1;//记录好后缀表边界位置的指标
char c;
if(shift == NULL)
{
printf("malloc failed!");
return 0;
}
c = *(ptrn + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它
*sptr = 1;//以最后一个字符为边界时，确定移动1的距离
pptr--;//边界移动到倒数第二个字符
while(sptr-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;
//该do...while循环完成以当前pptr所指的字符为边界时，要移动的距离
do{
while(p1 >= ptrn && *p1-- != c);//该空循环，寻找与最后一个字符c匹配的字符所指向的位置
p2 = ptrn + pLen - 2;
BM算法，是Berlekemp_Massey算法吗！？
没上面那么费劲吧？
想要的话，明天把我的给你.....
说明我只是为了求出结果，并没有考虑其它的因素，所以比较简单
晕，我以为是移位寄存器里的BM算法....