else q= i//while M//GEt next 4.29 LStrNode* ndex KMPSTring S, LString T, LStrNode*pos∥/链串上的KMP匹配 算法返回值为匹配的子串首指针 while(p&&q) if(q==Tlp->cdata=q->cdata q=q->succ, else q=q->next if(q) for(i=1; i <=Strlen (T): i++) p=p->1 return p3 }∥发现匹配后,要往回找子串的头 g//LIndex 4.30 void Get LRepsub( Stringtype S)/求S的最长重复子串的位置和长度 for( maxlen=0,j=1i<S[0计+》/串S2向右移i格 for(k=0j=1<=S[0]-i+为串S2的当前指针,此时串S1的当前指针为计j, 两指针同步移动 ifS[=S[+i)k++;用k记录连续相同的字符数 else k=0;∥失配时k归零 i( k>maxlen)∥发现了比以前发现的更长的重复子串 l51-j-k+1,lrs2=mrs+ L maxlen=k,∥作记录 i//fe} else q=q->next; }//while }//LGet_next 4.29 LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的 KMP 匹配 算法,返回值为匹配的子串首指针 { p=pos;q=T->succ; while(p&&q) { if(q==T||p->chdata==q->chdata) { p=p->succ; q=q->succ; } else q=q->next; }//while if(!q) { for(i=1;i<=Strlen(T);i++) p=p->next; return p; } //发现匹配后,要往回找子串的头 return NULL; }//LIndex_KMP 4.30 void Get_LRepSub(Stringtype S)//求 S 的最长重复子串的位置和长度 { for(maxlen=0,i=1;i<S[0];i++)//串 S2 向右移 i 格 { for(k=0,j=1;j<=S[0]-i;j++)//j 为串 S2 的当前指针,此时串 S1 的当前指针为 i+j, 两指针同步移动 { if(S[j]==S[j+i]) k++; //用 k 记录连续相同的字符数 else k=0; //失配时 k 归零 if(k>maxlen) //发现了比以前发现的更长的重复子串 { lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录 } }//for