k++;j++;
}
if(j==m) //既T[i..i+m-1]=P[0..m-1]
return i; //i为有效位移，否则查找下一个位移
}//endfor
return -1; //找不到有效位移，匹配失败
}//NaiveStrMatch
(3)算法分析
①最坏时间复杂度
该算法最坏情况下的时间复杂度为O((n-m+1)m)。TW.wiNgWIt.com
分析：当目标串和模式串分别是"a n-1 b"和"a m-1 b"时，对所有n-m+1个合法的位移，均要比较m个字符才能确定该位移是否为有
效位移，因此所需比较字符的总次数为(n-m+1)m。
②模式匹配算法的改进
朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移i是否为有效位移时，没有利用检查位移i-1，i,…,0时的部分匹配
结果。
若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏
时间控制在O(m+n)数量级上。具体可【参阅有关文献】。
5、链串上的子串定位运算
用结点大小为1的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移shift是结点地址而非整数，且单链
表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。具体算法如下：
LinkStrNode *LinkStrMatch(LinkString T,LinkString P)
{//在链串上求模式P在目标T首次出现的位置
LinkStrNode * shift,*t,*p;
shift=T; //shift表示位移
t=shift;p=P;
while(t&&p) {
if(t->data==p->data){ //继续比较后续结点中字符
t=t->next;
p=p->next;
}
else{ //已确定shift为无效位移
shift=shift->next; //模式右移，继续判定shift是否为有效位移
t=shift;
p=P;
}
}//endwhile
if(p==NULL)
return shift; //匹配成功
else
return NULL; //匹配失败
}
该算法的时间复杂度与顺序表上朴素的串匹配算法相同。
