要解决这个问题,需先计算模式串&n...
要解决这个问题,需先计算模式串 S = "aabaab" 的修正后 next
数组(即 nextval
数组),再通过该数组确定最大滑动距离。以下是详细步骤:
一、计算常规 next
数组
next
数组表示模式串中每个位置 i
匹配失败时,应回退的位置。计算规则为:
-
next[0] = -1
,next[1] = 0
-
对 i ≥ 2
,找到最长相等前缀和后缀的长度。
模式串索引与字符对应:
0:a, 1:a, 2:b, 3:a, 4:a, 5:b
计算过程:
-
next[0] = -1
-
next[1] = 0
-
i=2
:子串 "aa"
,前缀 "a"
和后缀 "a"
相等,next[2] = 1
-
i=3
:子串 "aab"
,无前缀后缀相等,next[3] = 0
-
i=4
:子串 "aaba"
,前缀 "a"
和后缀 "a"
相等,next[4] = 1
-
i=5
:子串 "aabaa"
,前缀 "aa"
和后缀 "aa"
相等,next[5] = 2
常规 next
数组:[-1, 0, 1, 0, 1, 2]
二、计算修正后 nextval
数组
为避免重复比较,优化得到 nextval
数组,规则为:
计算过程:
-
nextval[0] = -1
-
i=1
:S[1] = a
,next[1]=0
,S[0]=a
,相等 → nextval[1] = nextval[0] = -1
-
i=2
:S[2] = b
,next[2]=1
,S[1]=a
,不等 → nextval[2] = 1
-
i=3
:S[3] = a
,next[3]=0
,S[0]=a
,相等 → nextval[3] = nextval[0] = -1
-
i=4
:S[4] = a
,next[4]=1
,S[1]=a
,相等 → nextval[4] = nextval[1] = -1
-
i=5
:S[5] = b
,next[5]=2
,S[2]=b
,相等 → nextval[5] = nextval[2] = 1
nextval
数组:[-1, -1, 1, -1, -1, 1]
三、计算滑动距离
滑动距离 = 当前位置 i
- nextval[i]
,取最大值:
-
i=0
:0 - (-1) = 1
-
i=1
:1 - (-1) = 2
-
i=2
:2 - 1 = 1
-
i=3
:3 - (-1) = 4
-
i=4
:4 - (-1) = 5
(最大值)
-
i=5
:5 - 1 = 4
最长滑动距离为 5,对应选项 A。
答案:A. 5
登录后提交答案