對酒當歌,人生幾何? 譬如朝露,去日苦多

优质博客推荐

问题描述:母串S,子串T,求S[i]~S[n-1] (0<=i<n) ,与T的最长公共前缀extend[i]。

求解需要next数组辅助,next[i]表示next[i]~next[m-1]与next[0]~next[m-1]的最长公共前缀。

我们直接讨论在中间时匹配的情况。

已知:

1.假如我们extend已经求到了k,该求k+1了。

2.位置p代表extend[0,k]能匹配到的最远的位置,并且设取这个最大值的位置为po。

3.next数组已知,next[k+1]=len。

求extend数组

一。k+len<p

如上图

此时extend[k+1]=next[k+1]=len;

S[k+len+1]不会等于T[len],如果它们相等,那么就表示T[k+len-1-po]==T[len],那么next[k+1]=len+1,冲突,那么错误。

二。k+len>=p

因为我们最远才匹配到p,所以S[p+1]以后的字符和T[p-k]以后的字符一一开始匹配,直到失配为止。

如果得到的extend[k+1]+(k+1)大于P则要更新未知P和po。

然后求extend就结束了,而求next数组就和extend一样了,只不过把母串换了换。

 

标签: none

添加新评论